Алгоритм построения Эйлерова цикла
Описание алгоритма
Приведенный ниже псевдокод алгоритма находит Эйлеров цикл как в ориентированном графе, так и в неориентированном графе. Перед запуском алгоритма необходимо проверить граф на эйлеровость. Чтобы построить Эйлеров путь, нужно запустить функцию из вершины с нечетной степенью.
Псевдокод
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
Доказательство
Заметим, что рано или поздно алгоритм закончит свое выполнение, так как количество вершин, которое добавится в стек, не превышает количества ребер. А на каждой итерации цикла, в стек либо добавляется вершина, либо удаляется. Ясно, что в стеке всегда лежит какой-то путь и оператор print напечатает какой-то путь.
Пусть - это напечатанный после окончания работы алгоритма путь. Заметим, что вершина напечатается только в том случае, если все ребра, инцидентные , уже пройдены. Отсюда следует, что для любой вершины из все инцидентные ей ребра содержатся в . В ходе алгоритма для каждой вершины в стек попадают все смежные с ней вершины, а так как алгоритм работает до опустошения стека, все они в итоге попадут в . Поскольку эйлеров граф содержит не больше одной компоненты связности с более чем одной вершиной, то содержит все ребра графа. А значит напечатанный путь эйлеров.
Рекурсивная реализация
findPath(v):
for (v, u) from E
remove (v, u)
findPath(u)
print v
Время работы
Если реализовать удаление ребер за , то алгоритм будет работать за .
