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