Алгоритм построения Эйлерова цикла — различия между версиями
Lehanyich (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показано 6 промежуточных версий 6 участников) | |||
Строка 2: | Строка 2: | ||
=== Описание алгоритма === | === Описание алгоритма === | ||
Алгоритм находит [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров цикл]] как в [[Ориентированный граф|ориентированном]], так и в [[Основные определения теории графов#Неориентированные графы|неориентированном графе]]. Перед запуском алгоритма необходимо [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|проверить граф на эйлеровость]]. Чтобы построить [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров путь]], нужно запустить алгоритм из вершины с нечетной степенью.<br> | Алгоритм находит [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров цикл]] как в [[Ориентированный граф|ориентированном]], так и в [[Основные определения теории графов#Неориентированные графы|неориентированном графе]]. Перед запуском алгоритма необходимо [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|проверить граф на эйлеровость]]. Чтобы построить [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров путь]], нужно запустить алгоритм из вершины с нечетной степенью.<br> | ||
− | Алгоритм напоминает поиск в | + | Алгоритм напоминает поиск в глубину. Главное отличие состоит в том, что пройденными помечаются не вершины, а ребра графа. Начиная со стартовой вершины <tex>v</tex> строим путь, добавляя на каждом шаге не пройденное еще ребро, смежное с текущей вершиной. Вершины пути накапливаются в [[Стек | стеке]] <tex>S</tex>. Когда наступает такой момент, что для текущей вершины <tex>w</tex> все инцидентные ей ребра уже пройдены, записываем вершины из <tex>S</tex> в ответ, пока не встретим вершину, которой инцидентны не пройденные еще ребра. Далее продолжаем обход по не посещенным ребрам. |
=== Псевдокод === | === Псевдокод === | ||
Строка 30: | Строка 30: | ||
<tex>v = u</tex> | <tex>v = u</tex> | ||
'''break''' | '''break''' | ||
− | + | <tex>S</tex>.push(<tex>v</tex>) <font color=darkgreen>// <tex>S</tex> {{---}} стек</font> | |
− | |||
'''while not''' <tex>S</tex>.empty() | '''while not''' <tex>S</tex>.empty() | ||
<tex>w = </tex> <tex>S</tex>.top() | <tex>w = </tex> <tex>S</tex>.top() | ||
+ | found_edge = '''False''' | ||
'''for''' <tex>u : u \in V</tex> | '''for''' <tex>u : u \in V</tex> | ||
'''if''' (<tex>w, u</tex>) <tex>\in E</tex> <font color=darkgreen> // нашли ребро, по которому ещё не прошли</font> | '''if''' (<tex>w, u</tex>) <tex>\in E</tex> <font color=darkgreen> // нашли ребро, по которому ещё не прошли</font> | ||
<tex>S</tex>.push(<tex>u</tex>) <font color=darkgreen> // добавили новую вершину в стек</font> | <tex>S</tex>.push(<tex>u</tex>) <font color=darkgreen> // добавили новую вершину в стек</font> | ||
<tex>E</tex>.remove(<tex>w, u</tex>) | <tex>E</tex>.remove(<tex>w, u</tex>) | ||
+ | found_edge = '''True''' | ||
'''break''' | '''break''' | ||
− | '''if''' | + | '''if''' '''not''' found_edge |
<tex>S</tex>.pop() <font color=darkgreen> // не нашлось инцидентных вершине <tex>w</tex> рёбер, по которым ещё не прошли</font> | <tex>S</tex>.pop() <font color=darkgreen> // не нашлось инцидентных вершине <tex>w</tex> рёбер, по которым ещё не прошли</font> | ||
print(<tex>w</tex>) | print(<tex>w</tex>) | ||
Строка 77: | Строка 78: | ||
Чтобы реализовать поиск за <tex>O(1)</tex>, для хранения графа следует использовать списки смежных вершин; для удаления достаточно добавить всем ребрам свойство <tex>\mathtt{deleted}</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> | ||
== См. также == | == См. также == | ||
* [[Гамильтоновы графы]] | * [[Гамильтоновы графы]] | ||
− | * [[Покрытие | + | * [[Покрытие рёбер графа путями]] |
* [[Произвольно вычерчиваемые из заданной вершины графы]] | * [[Произвольно вычерчиваемые из заданной вершины графы]] | ||
Строка 86: | Строка 108: | ||
* [http://e-maxx.ru/algo/euler_path Статья про нахождение Эйлерова пути с реализацией на С++ на сайте e-maxx.ru] | * [http://e-maxx.ru/algo/euler_path Статья про нахождение Эйлерова пути с реализацией на С++ на сайте e-maxx.ru] | ||
* [http://ивтб.рф/exams/саод/36.htm Статья про нахождение Эйлерова пути с реализацией на Pascal на сайте ивтб.рф] | * [http://ивтб.рф/exams/саод/36.htm Статья про нахождение Эйлерова пути с реализацией на Pascal на сайте ивтб.рф] | ||
+ | * [https://www.youtube.com/watch?v=ryw059C6oK8 Видео-лекция А.С.Станкевича про нахождение Эйлерова цикла с реализацией на C++ на сайте youtube.com] | ||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Обходы графов]] | [[Категория: Обходы графов]] | ||
[[Категория: Эйлеровы графы]] | [[Категория: Эйлеровы графы]] |
Текущая версия на 19:20, 4 сентября 2022
Содержание
Алгоритм
Описание алгоритма
Алгоритм находит Эйлеров цикл как в ориентированном, так и в неориентированном графе. Перед запуском алгоритма необходимо проверить граф на эйлеровость. Чтобы построить Эйлеров путь, нужно запустить алгоритм из вершины с нечетной степенью.
Алгоритм напоминает поиск в глубину. Главное отличие состоит в том, что пройденными помечаются не вершины, а ребра графа. Начиная со стартовой вершины строим путь, добавляя на каждом шаге не пройденное еще ребро, смежное с текущей вершиной. Вершины пути накапливаются в стеке . Когда наступает такой момент, что для текущей вершины все инцидентные ей ребра уже пройдены, записываем вершины из в ответ, пока не встретим вершину, которой инцидентны не пройденные еще ребра. Далее продолжаем обход по не посещенным ребрам.
Псевдокод
Код проверки графа на эйлеровость:
boolean checkForEulerPath(): int OddVertexfor if ( ) mod OddVertex++ if OddVertex // если количество вершин с нечетной степенью больше двух, то граф не является эйлеровым return false boolean visited( , false) // массив инициализируется значениями false for if ( ) dfs( , visited) break for if ( ) and not visited[ ] // если количество компонент связности, содержащие ребра, больше одной, return false // то граф не является эйлеровым return true // граф является эйлеровым
Код построения эйлерова пути:
function findEulerPath(): // если граф является полуэйлеровым, то алгоритм следует запускать из вершины нечетной степени for if ( ) mod break .push( ) // — стек while not .empty() .top() found_edge = False for if ( ) // нашли ребро, по которому ещё не прошли .push( ) // добавили новую вершину в стек .remove( ) found_edge = True break if not found_edge .pop() // не нашлось инцидентных вершине рёбер, по которым ещё не прошли print( )
Доказательство корректности
Лемма: |
Данный алгоритм проходит по каждому ребру, причем ровно один раз. |
Доказательство: |
Допустим, что в момент окончания работы алгоритма имеются еще не пройденные ребра. Поскольку граф связен, должно существовать хотя бы одно не пройденное ребро, инцидентное посещенной вершине. Но тогда эта вершина не могла быть удалена из стека Но так как после прохода по ребру оно удаляется, то пройти по нему дважды алгоритм не может. , и он не мог стать пустым. Значит алгоритм пройдёт по всем рёбрам хотя бы один раз. |
Вершина
Лемма: |
Напечатанный путь — корректный маршрут в графе, в котором каждые две соседние вершины и будут образовывать ребро . |
Доказательство: |
Будем говорить, что ребро представлено в или , если в какой-то момент работы алгоритма вершины и находятся рядом. Каждое ребро графа представлено в . Рассмотрим случай, когда из в перемещена вершина , а следующей в лежит . Возможны 2 варианта:
|
Теорема: |
Данный алгоритм находит корректный эйлеров путь. |
Доказательство: |
Из предыдущих лемм следует, что | — искомый эйлеров путь и алгоритм работает корректно.
Рекурсивная реализация
function findEulerPath(: Vertex): for remove findEulerPath( ) print( )
Время работы
Если реализовать поиск ребер инцидентных вершине и удаление ребер за
Чтобы реализовать поиск за , для хранения графа следует использовать списки смежных вершин; для удаления достаточно добавить всем ребрам свойство бинарного типа.
Рекурсивная реализация за
Заведём 2 массива:
- посещено ли ребро с индексом
(массив нужен, чтобы за проверять, доступно ребро или нет)
- индекс первой вершины в списке смежных вершин, такой что ребро не посещено
(массив нужен, чтобы в среднем за находить доступное ребро)
Изначально оба массива заполнены нулями.
Граф будем хранить в виде списков смежных вершин. Для каждой вершины
- индекс ребра
- номер смежной вершины
После ввода графа нужно запустить
function euler(): while (first[ ] < g[ ].size()): //если first[ ] = g[ ].size, рёбра во все смежные вершины уже посещены , = g[ ][first[ ]] first[ ] += 1 if (!vis[ ]):
vis[ ] = true
euler( )
print( )