В чем заключается принцип работы алгоритма поиска пути Эйлера?

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

Алгоритм похож на поиск в глубину, но главное отличие в том, что как пройденные помечаются не вершины, а рёбра графа. intuit.ru neerc.ifmo.ru

Процесс происходит так: intuit.ru

1. Начиная с произвольно выбранной стартовой вершины, строят путь, выбирая каждый раз для дальнейшего продвижения ещё не пройденное ребро. intuit.ru
2. Вершины пути накапливаются в стеке. intuit.ru
3. Через некоторое количество шагов наступает тупик: все рёбра, инцидентные активной (последней посещённой) вершине, уже пройдены. intuit.ru
4. Для обнаружения ещё не пройденных рёбер возвращаются по пройденному пути, перекладывая вершины из стека в другой стек, пока не встретят вершину, которой инцидентно непройденное ребро. intuit.ru
5. Тогда возобновляют движение вперёд по непройденным рёбрам, пока не достигнут нового тупика и так далее. intuit.ru
6. Процесс заканчивается, когда в очередном тупике обнаруживают, что стек пуст. intuit.ru В этот момент в стеке находится последовательность вершин эйлерова цикла. intuit.ru