Алгоритм построения Эйлерова цикла

Описание алгоритма

Приведенный ниже псевдокод алгоритма находит Эйлеров цикл как в ориентированном графе, так и в неориентированном графе. Перед запуском алгоритма необходимо проверить граф на эйлеровость. Чтобы построить Эйлеров путь, нужно запустить функцию из вершины с нечетной степенью.

Псевдокод

 findPath(v):
   S.clear()
   S.add(v)
   while not stack.isEmpty():
     w := S.top()
     if E contains (w, u):
       S.add(u)
       remove(w, u)
     else:
       S.pop()
       print w

Доказательство

Пусть [math]P[/math] - напечатанный путь. Заметим, что первой в [math]S[/math] помещается вершина [math]v[/math], и она будет последней перемещена из [math]S[/math] в [math]P[/math]. Следовательно, она будет последней вершиной в [math]P[/math]. Далее, как было отмечено выше, первый раз, когда обнаружится, что все инцидентные активной вершине ребра пройдены, активной будет стартовая вершина [math]v[/math]. Значит, эта вершина будет первой перемещена из [math]S[/math] в [math]P[/math]. Итак, по окончании работы алгоритма в начале и в конце последовательности вершин, содержащейся в [math]P[/math], находится вершина [math]v[/math]. Иначе говоря, если эта последовательность представляет маршрут, то этот маршрут замкнут.
Покажем, что маршрут замкнут.
Отметим, что в конечном итоге каждое ребро будет пройдено. Действительно, допустим, что в момент окончания работы алгоритма имеются еще не пройденные ребра. Поскольку граф связен, должно существовать хотя бы одно непройденное ребро, инцидентное посещенной вершине. Но тогда эта вершина не могла быть удалена из [math]S[/math], и [math]S[/math] не мог стать пустым. [math] \Box [/math]

Рекурсивная реализация

 findPath(v):
   for (v, u) from E
     remove (v, u)
     findPath(u)
   print v

Время работы

Если реализовать удаление ребер за [math]O(1)[/math], то алгоритм будет работать за [math]O(E)[/math].

См. также

• Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
• Статья про нахождение Эйлерова пути с реализацией на С++ на сайте e-maxx.ru