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