17
правок
Изменения
м
<tex>S</tex>.pop() print(<tex>w</tex>)
Нет описания правки
'''boolean''' checkForEulerPath():
'''int''' numberOfOdd = 0
'''for''' <tex>v </tex> '''in''' <tex>V</tex> '''if''' vertexDegree(<tex>\operatorname{deg} v) </tex> '''mod''' 2 == 1
numberOfOdd = numberOfOdd + 1
'''if''' numberOfOdd > 2 <font color=darkgreen>// если количество вершин с нечетной степенью больше двух, то граф не является эйлеровым</font>
'''return''' ''false''
'''boolean''' vis[sizeOf <tex>V</tex>] <font color=darkgreen>// инициализировать массив значениями ''false''</font>
'''for''' <tex>v </tex> '''in''' <tex>V</tex> '''if''' vertexDegree(<tex>\operatorname{deg} v) </tex> > 0 dfs(<tex>v</tex>, vis)
break
'''for''' <tex>v </tex> '''in''' <tex>V</tex> '''if''' vertexDegree(<tex>\operatorname{deg} v) </tex> > 0 '''and''' '''not''' vis[<tex>v</tex>] <font color=darkgreen>// если количество компонент связности, содержащие ребра, больше одной,</font> '''return''' ''false'' <font color=darkgreen> // то граф не является эйлеровым</font> '''return''' ''true'' // граф является эйлеровым <font color=darkgreen>// Вспомогательные функции:граф является эйлеровым</font> '''function''' dfs(v : Vertex, vis[] : '''boolean'''): vis[v] = ''true'' '''for''' (v, u) '''in''' <tex>E</tex> '''if not''' vis[u] dfs(u, vis) '''int''' vertexDegree(v : Vertex): '''int''' count = 0 '''for''' (v, u) '''in''' <tex>E</tex> count = count + 1 '''return''' count
'''Код построения эйлерова пути:'''
'''function''' findEulerPath(<tex>v </tex> : Vertex): <font color=darkgreen> // если граф является полуэйлеровым, то алгоритм следует запускать из вершины нечетной степени </font> Stack <tex>S</tex> S.push(<tex>Sv</tex>.push(v) '''while not''' <tex>S</tex>.isEmpty() w = <tex>Sw</tex>= S.top() '''if''' exists <tex>(w, u) </tex> '''in''' <tex>E</tex> S.push(<tex>Su</tex>.push(u) remove<tex>(w, u)</tex>
'''else'''
</font>
== Рекурсивная реализация ==
<font size=2>
'''function''' findEulerPath(<tex>v</tex> : Vertex): '''for''' <tex>(v, u) </tex> '''in''' <tex>E</tex> remove<tex>(v, u)</tex> findEulerPath(<tex>u</tex>) print(<tex>v</tex>)
</font>
