27
правок
Изменения
→Псевдокод
'''Код проверки графа на эйлеровость:'''
'''boolean''' checkForEulerPath():
'''int''' numberOfOdd OddVertex <tex>= 0</tex> '''for''' <tex>v : v</tex> <tex>\in</tex> <tex>V</tex> '''if''' <tex>\operatorname{deg} </tex>(<tex>v</tex> ) '''mod''' <tex>2 == 1</tex> numberOfOdd = numberOfOdd OddVertex++ 1 '''if''' numberOfOdd OddVertex <tex> > 2 </tex><font color=darkgreen>// если количество вершин с нечетной степенью больше двух, то граф не является эйлеровым</font>
'''return''' ''false''
'''boolean''' vis[visited(<tex>|V|</tex>] , ''false'') <font color=darkgreen>// инициализировать массив инициализируется значениями ''false''</font> '''for''' <tex>v : v</tex> <tex>\in</tex> <tex>V</tex> '''if''' <tex>\operatorname{deg} </tex>(<tex>v</tex>) <tex> > 0</tex> dfs(<tex>v</tex>, visvisited) '''break''' '''for''' <tex>v : v</tex> <tex>\in</tex> <tex>V</tex> '''if''' <tex>\operatorname{deg} </tex>(<tex>v</tex>) <tex> > 0 </tex> '''and''' '''not''' visvisited[<tex>v</tex>] <font color=darkgreen>// если количество компонент связности, содержащие ребра, больше одной,</font>
'''return''' ''false'' <font color=darkgreen> // то граф не является эйлеровым</font>
'''return''' ''true'' <font color=darkgreen>// граф является эйлеровым</font>
'''Код построения эйлерова пути:'''
'''function''' findEulerPath(<tex>v</tex> : Vertex): <font color=darkgreen> // если граф является полуэйлеровым, то алгоритм следует запускать из вершины нечетной степени </font> '''for''' <tex>u : u \in V</tex> '''if''' <tex>\operatorname{deg}</tex>(<tex>u</tex>) '''mod''' <tex>2 == 1</tex> <tex>v = u</tex> '''break''' Stack <tex>S</tex> <tex>S</tex>.push(<tex>v</tex>) '''while not''' <tex>S</tex>.isEmptyempty() <tex>w= </tex> = <tex>S</tex>.top() '''for''' <tex>u : u \in V</tex> '''if''' (<tex>(w, u)</tex> ) <tex>\inE</tex> <font color=darkgreen> // нашли ребро, по которому ещё не прошли</font> <tex>ES</tex> S.push(<tex>u</tex>)<font color=darkgreen> // добавили новую вершину в стек</font> <tex>E</tex>.remove (<tex>(w, u)</tex>) '''break''' '''elseif''' <tex> w == S</tex>.top() <tex>S</tex>.pop()<font color=darkgreen> // не нашлось инцидентных вершине <tex>w</tex> рёбер, по которым ещё не прошли</font>
print(<tex>w</tex>)
</font>
