Как алгоритм Эйлера помогает в обходе графов?

Алгоритм Эйлера помогает в обходе графов, позволяя найти эйлеров цикл — замкнутый маршрут, в котором каждое ребро графа встречается точно один раз. intuit.ru

Алгоритм работает так: начиная с произвольно выбранной стартовой вершины, строят путь, выбирая каждый раз для дальнейшего продвижения ещё не пройденное ребро. intuit.ru Главное отличие от поиска в глубину в том, что как пройденные помечаются именно рёбра, а не вершины. intuit.ru

Некоторые особенности алгоритма:

• Одна и та же вершина может посещаться несколько раз, но каждое ребро проходится не более одного раза. intuit.ru
• Вершины пути накапливаются в стеке. neerc.ifmo.ru intuit.ru
• Через некоторое количество шагов наступает тупик: все рёбра, инцидентные активной (последней посещённой) вершине, уже пройдены. intuit.ru
• Для обнаружения ещё не пройденных рёбер возвращаются по пройденному пути, пока не встретят вершину, которой инцидентно непройденное ребро. intuit.ru
• Тогда возобновляют движение вперёд по непройденным рёбрам, пока не дойдёт до нового тупика, и так далее. intuit.ru
• Процесс заканчивается, когда в очередном тупике обнаруживается, что стек пуст. intuit.ru В этот момент в стеке находится последовательность вершин эйлерова цикла. intuit.ru