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

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

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

Псевдокод

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

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

Заметим, что рано или поздно алгоритм закончит свое выполнение, так как количество вершин, которое добавится в стек, не превышает количества ребер. А на каждой итерации цикла, в стек либо добавляется вершина, либо удаляется. Ясно, что в стеке всегда лежит какой-то путь и оператор print напечатает какой-то путь.

Пусть [math]P[/math] - это напечатанный после окончания работы алгоритма путь. Заметим, что вершина [math]w[/math] напечатается только в том случае, если все ребра, инцидентные [math]w[/math], уже пройдены. Отсюда следует, что для любой вершины из [math] P [/math] все инцидентные ей ребра содержатся в [math] P [/math]. В ходе алгоритма для каждой вершины в стек попадают все смежные с ней вершины, а так как алгоритм работает до опустошения стека, все они в итоге попадут в [math] P [/math]. Поскольку эйлеров граф содержит не больше одной компоненты связности с более чем одной вершиной, то [math] P [/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