17
правок
Изменения
Нет описания правки
== Псевдокод ==
<font size=32>'''Код проверки графа на эйлеровость:''' function dfs(v : Vertex, vis[] : boolean): vis[v] = true for (v, u) in E: if not vis[u]: dfs(u, vis) int vertexDegree(v : Vertex): int count = 0 for (v, u) in E: 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: findPath// если количество вершин с нечетной степенью больше двух, то граф не является эйлеровым 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 // то граф не является эйлеровым S.clearreturn true // граф является эйлеровым '''Код построения эйлерова цикла:''' function findEulerPath(v : Vertex): SStack stack stack.addpush(v) while not Sstack.isEmpty(): w := Sstack.top() if E containsexist (w, u)in E: S stack.addpush(u) remove(w, u) else: S stack.pop() print (w)
</font>
== Рекурсивная реализация ==
<font size=32> findPath findEulerPath(v): for (v, u) from in E: remove(v, u) findPath findEulerPath(u)
print v
</font>
== Время работы ==
Если реализовать удаление ребер за <tex>O(1)</tex>(для этого для каждого ребра достаточно добавить свойство deleted типа boolean), то алгоритм будет работать за <tex>O(E)</tex>.
== См. также ==
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [[Покрытие ребер графа путями]]
== Источники информации ==
* [http://ru.wikipedia.org/wiki/Эйлеров_цикл Википедия {{---}} Эйлеров цикл]
* [http://e-maxx.ru/algo/euler_path Статья про нахождение Эйлерова пути с реализацией на С++ на сайте e-maxx.ru]
* [http://ивтб.рф/exams/саод/36.htm Статья про нахождение Эйлерова пути с реализацией на Pascal на сайте ивтб.рф]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
