Что делает: ищет цикл без повторяющихся ребер, проходящий через каждое ребро графа

Общая идея:

1. Проверить на то, Эйлеров ли граф
2. Через рекурсию, удаляя инцидентные рёбра, вывести вершинки после окончания ⇒ получим цикл

Теория (НЕ ПРОПУСКАТЬ А ТО УЕБУ):

Эйлеров путь — путь, проходящий по всем ребрам графа и при том только по одному разу (если есть 2 вершины с нечетной степенью, то ∃ Эйлеров путь, но нет  эйлерова цикла)

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

Эйлеров граф — граф, содержащий Эйлеров цикл

‼ Перед тем, как искать Эйлеров цикл, необходимо проверить, что граф - Эйлеров. Для этого существует критерий Эйлеровости:

Граф Эйлеров, если:

Все вершины имеют чётную степень

Все компоненты связности кроме одной не содержат рёбер

Реализация:

1) Проверить по критерию наличие Эйлерова цикла в графе
2) Начать из любой вершины:
	*Рекурсия* от вершины v:
		а) посмотреть смежную вершину u
		б) удалить ребро (v,u)
		в) запустить [рекурсивно] от вершины u
	Окончание *рекурсии* для каждой вершины: вывести вершину

Алгоритм напоминает поиск в глубину (представляет собой модификацию поиска в глубину, т.к. вместо того чтобы двигаться от одной вершины к другой, мы двигаемся от одного ребра к другому до тех пор, пока не пройдем по каждому ребру (по ребру можем пройти только один раз)). Главное отличие состоит в том, что пройденными помечаются не вершины, а ребра графа.

Используем два списка для нахождения цикла: стек, в котором будем записывать посещенные вершины, и список вершин Эйлерова цикла (наш ответ). Пройденные ребра удаляем из графа.

Начиная с любой стартовой вершины v строим путь, добавляя на каждом шаге ещё не пройденное ребро, инцидентное текущей вершине. Пройденные вершины пути пушим в стек Stack. Когда наступает такой момент, что для текущей вершины v все инцидентные ей ребра уже пройдены, пушим вершины из Stack в ответ (и удаляем их из стека), пока не встретим вершину, которой инцидентны ещё не пройденные ребра. Продолжаем обход по не посещённым ребрам.

Визуализация: этим я займусь чуть попозже