17
правок
Изменения
Отформатирован псевдокод, добавлена проверка на эйлеровость, добавлено описание удаления ребра за O(1), добавлены источники информации
<font size=2>
'''Код проверки графа на эйлеровость:'''
'''boolean''' checkForEulerPath(): '''int''' numberOfOdd = 0 '''for''' v '''in''' <tex>V</tex> '''if''' vertexDegree(v) '''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''' v '''in''' <tex>V</tex> '''if''' vertexDegree(v) > 0 dfs(v, vis) break '''for''' v '''in''' <tex>V</tex> '''if''' vertexDegree(v) > 0 '''and''' '''not''' vis[v] <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 boolean checkForEulerPath(): int numberOfOdd = 0 for v in V: if vertexDegree(v) % 2 == 1: numberOfOdd = numberOfOdd + 1 if numberOfOdd > 2: // если количество вершин с нечетной степенью больше двух, то граф не является эйлеровым return false boolean vis[V.length] // все элементы инициализируются значениями false for v in V: if vertexDegree(v) > 0: dfs(v, vis) break for v in V: if vertexDegree(v) > 0 and vis[v] == false: // если количество компонент связности, содержащие ребра, больше одной, return false // то граф не является эйлеровым return true // граф является эйлеровым
'''Код построения эйлерова цикла:'''
'''function ''' findEulerPath(v : Vertex):
Stack stack
stack.push(v)
'''while not ''' stack.isEmpty():
w = stack.top()
'''if exist ''' exists (w, u) '''in ''' <tex>E:</tex>
stack.push(u)
remove(w, u)
'''else '''
stack.pop()
print(w)
== Рекурсивная реализация ==
<font size=2>
'''function''' findEulerPath(v): '''for ''' (v, u) '''in ''' <tex>E:</tex>
remove(v, u)
findEulerPath(u)
print (v)
</font>
