Алгоритм построения Эйлерова цикла — различия между версиями
(→Доказательство) |
(→Псевдокод) |
||
| Строка 5: | Строка 5: | ||
<font size=3> | <font size=3> | ||
findPath(v): | findPath(v): | ||
| − | + | S.clear() | |
| − | + | S.add(v) | |
while not stack.isEmpty(): | while not stack.isEmpty(): | ||
| − | w := | + | w := S.top() |
if E contains (w, u): | if E contains (w, u): | ||
| − | + | S.add(u) | |
remove(w, u) | remove(w, u) | ||
else: | else: | ||
| − | + | S.pop() | |
print w | print w | ||
</font> | </font> | ||
Версия 17:49, 23 февраля 2012
Содержание
Описание алгоритма
Приведенный ниже псевдокод алгоритма находит Эйлеров цикл как в ориентированном графе, так и в неориентированном графе. Перед запуском алгоритма необходимо проверить граф на эйлеровость. Чтобы построить Эйлеров путь, нужно запустить функцию из вершины с нечетной степенью.
Псевдокод
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
Время работы
Если реализовать удаление ребер за , то алгоритм будет работать за .
