Изменения
Добавлена реализация алгоритма поиска Эйлерова цикла за O(E)
=== Описание алгоритма ===
Алгоритм находит [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров цикл]] как в [[Ориентированный граф|ориентированном]], так и в [[Основные определения теории графов#Неориентированные графы|неориентированном графе]]. Перед запуском алгоритма необходимо [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|проверить граф на эйлеровость]]. Чтобы построить [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров путь]], нужно запустить алгоритм из вершины с нечетной степенью.<br>
Алгоритм напоминает поиск в ширинуглубину. Главное отличие состоит в том, что пройденными помечаются не вершины, а ребра графа. Начиная со стартовой вершины <tex>v</tex> строим путь, добавляя на каждом шаге не пройденное еще ребро, смежное с текущей вершиной. Вершины пути накапливаются в [[Стек | стеке]] <tex>S</tex>. Когда наступает такой момент, что для текущей вершины <tex>w</tex> все инцидентные ей ребра уже пройдены, записываем вершины из <tex>S</tex> в ответ, пока не встретим вершину, которой инцидентны не пройденные еще ребра. Далее продолжаем обход по не посещенным ребрам.
=== Псевдокод ===
Чтобы реализовать поиск за <tex>O(1)</tex>, для хранения графа следует использовать списки смежных вершин; для удаления достаточно добавить всем ребрам свойство <tex>\mathtt{deleted}</tex> бинарного типа.
=== Рекурсивная реализация за <tex>O(E)</tex> ===
Заведём 2 массива: <tex>vis</tex> и <tex>first</tex> <br>
<tex>vis[i] (bool)</tex> - посещено ли ребро с индексом <tex>i</tex> <tex>(i \in 0..(E-1))</tex><br>
(массив нужен, чтобы за <tex>O(1)</tex> проверять, доступно ребро или нет) <br>
<tex>first[u] (int)</tex> - индекс первой вершины <tex>v</tex> в списке смежных вершин, такой что ребро <tex>(u,v)</tex> не посещено <tex>(u \in 0..(V-1))</tex><br>
(массив нужен, чтобы в среднем за <tex>O(1)</tex> находить доступное ребро) <br>
Изначально оба массива заполнены нулями. <br>
Граф будем хранить в виде списков смежных вершин. Для каждой вершины <tex>u</tex> построим список <tex>g[u]</tex> из пар вида <tex>(i,v)</tex> <br>
<tex>i</tex> - индекс ребра <tex>(u,v)</tex> <br>
<tex>v</tex> - номер смежной вершины <br>
После ввода графа нужно запустить <tex>euler(0)</tex> или от любой другой вершины. <br>
<font size=2>
'''function''' euler(<tex>u</tex>):
'''while''' (first[<tex>u</tex>] < g[<tex>u</tex>].size()): <font color=darkgreen> //если first[<tex>u</tex>] = g[<tex>u</tex>].size, рёбра во все смежные вершины уже посещены</font>
<tex>i</tex>,<tex>v</tex> = g[<tex>u</tex>][first[<tex>u</tex>]]
first[<tex>u</tex>] += 1
'''if''' (!vis[<tex>i</tex>]):<br> vis[<tex>i</tex>] = true<br> euler(<tex>v</tex>)<br> print(<tex>v</tex>)
</font> <br>
== См. также ==
* [[Гамильтоновы графы]]
* [http://e-maxx.ru/algo/euler_path Статья про нахождение Эйлерова пути с реализацией на С++ на сайте e-maxx.ru]
* [http://ивтб.рф/exams/саод/36.htm Статья про нахождение Эйлерова пути с реализацией на Pascal на сайте ивтб.рф]
* [https://www.youtube.com/watch?v=ryw059C6oK8 Видео-лекция А.С.Станкевича про нахождение Эйлерова цикла с реализацией на C++ на сайте youtube.com]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
[[Категория: Эйлеровы графы]]
