Эйлеров путь: когда он существует и как найти его за O(E)

Короткий ответ. Эйлеров путь это маршрут, который проходит каждое ребро графа ровно один раз. Существует он только при определённом числе вершин с нечётной степенью. Находят его алгоритмом Хирхольцера за O(E). Ниже условия существования, код на Python и задача Reconstruct Itinerary.

Что такое эйлеров путь и эйлеров цикл?

Эйлеров путь проходит каждое ребро ровно один раз. Начало и конец могут быть разными вершинами.

Эйлеров цикл это то же самое, но маршрут возвращается в стартовую вершину.

Вершины при этом можно посещать сколько угодно раз. Ограничение только на рёбра. Это главное отличие от гамильтонова пути, где каждая вершина ровно один раз.

Когда эйлеров путь существует?

Ответ даёт подсчёт степеней. Степень вершины это число рёбер при ней.

Граф	Эйлеров цикл	Эйлеров путь
Неориентированный	Все степени чётные	Ровно 0 или 2 нечётные вершины
Ориентированный	У каждой вершины вход равен выходу	Одна вершина с выход - вход = 1, одна с вход - выход = 1, остальные равны
Плюс всегда	Все рёбра в одной компоненте	Все рёбра в одной компоненте

Если нечётных вершин две, путь идёт из одной в другую. Если ноль, старт где угодно.

Проверка занимает один проход по рёбрам. Её делают до поиска, а не после.

Как работает алгоритм Хирхольцера?

Идея одна. Идём по неиспользованным рёбрам, пока идётся. Тупики записываем в ответ.

• Стартуем в подходящей вершине. Кладём её в стек.
• Пока у вершины на вершине стека есть неиспользованное ребро, идём по нему. Новую вершину кладём в стек.
• Рёбер нет, значит вершина тупик. Снимаем её со стека и дописываем в ответ.
• Стек пуст, ответ готов. Его надо развернуть.

Разворот нужен потому, что тупики записываются с конца. Первым в ответ попадает последняя вершина маршрута.

Как написать эйлеров путь на Python?

Ориентированный граф задан списком рёбер. Ищем путь, старт передаём явно.

def euler_path(edges, start):
    graph = {}
    for a, b in edges:
        graph.setdefault(a, []).append(b)

    stack = [start]
    path = []

    while stack:
        v = stack[-1]
        if graph.get(v):
            stack.append(graph[v].pop())
        else:
            path.append(stack.pop())

    return path[::-1]

Три детали, на которых держится код.

• graph[v].pop() удаляет ребро при использовании. Второй раз по нему не пройти.
• Стек хранит текущий маршрут. Ответ собирается из тупиков.
• Сложность O(E): каждое ребро снимается один раз.

Для неориентированного графа ребро надо удалять с обеих сторон. Проще хранить рёбра с номерами и помечать использованные.

Как решить Reconstruct Itinerary через эйлеров путь?

Условие. Даны билеты в виде пар «откуда, куда». Все начинаются из JFK. Построй маршрут, который использует каждый билет один раз. При нескольких вариантах бери лексикографически меньший.

Каждый билет это ребро. «Использовать каждый один раз» это эйлеров путь. Условие гарантирует, что он существует.

Лексикографический порядок даёт одна правка. Списки соседей сортируем по убыванию, тогда pop() снимает самый маленький.

def find_itinerary(tickets):
    graph = {}
    for a, b in sorted(tickets, reverse=True):
        graph.setdefault(a, []).append(b)
    return euler_path_from(graph, "JFK")

Проследим на билетах JFK→SFO, JFK→ATL, SFO→ATL, ATL→JFK, ATL→SFO.

• Из JFK меньший сосед ATL. Из ATL меньший JFK. Из JFK остался SFO. Из SFO в ATL. Из ATL в SFO.
• SFO тупик, записываем. ATL, SFO, JFK, ATL, JFK записываются по мере возврата.
• Разворот: JFK, ATL, JFK, SFO, ATL, SFO.

Жадный обход без стека тут ломается. Он уйдёт в ATL→JFK→SFO→ATL→SFO и потеряет билет. Стек с тупиками это чинит.

Как узнать эйлеров путь в условии задачи?

Слова, которые на него указывают.

• «Использовать каждый билет, каждую дорогу, каждое ребро ровно один раз».
• «Нарисовать фигуру, не отрывая руки».
• «Собрать цепочку из всех костяшек домино».
• «Обойти все улицы и вернуться» для почтальона или уборочной машины.
• «Соединить слова так, чтобы последняя буква совпадала с первой».

Общий признак: ограничение стоит на рёбрах, а не на вершинах. Если «каждый город один раз», это уже другая задача, и она NP-полная.

Сигналы, соседи и шаблоны на шести языках на странице эйлерова пути.

Как объяснить эйлеров путь на собеседовании?

Три фразы до кода.

• «Каждое ребро один раз, значит эйлеров путь. Сначала проверю степени.»
• «Иду по неиспользованным рёбрам, тупики дописываю в ответ, в конце разворачиваю.»
• «Каждое ребро снимается один раз, поэтому O(E).»

Потом код. Потом трассировка на пяти рёбрах, как выше. Про разворот сказать отдельно, о нём забывают.

На чём ломается эйлеров путь?

• Не проверены степени. Алгоритм вернёт путь по части рёбер, и он будет выглядеть правильным.
• Старт не в нечётной вершине. Путь оборвётся раньше времени.
• Забыт разворот ответа. Маршрут выходит задом наперёд.
• Неориентированное ребро удалено с одной стороны. Его пройдут дважды.

Как узнавать такие задачи по условию, а не по названию, разобрано в статье про паттерны.

Вопросы и ответы

Чем эйлеров путь отличается от гамильтонова?

Эйлеров проходит все рёбра, гамильтонов все вершины. Первый ищется за O(E), второй NP-полный.

Какая сложность у алгоритма Хирхольцера?

O(V + E) по времени и O(E) по памяти на стек и ответ.

Можно ли найти эйлеров путь обычным DFS?

Обычный DFS с откатами работает, но может быть экспоненциальным. Хирхольцер без откатов, поэтому линейный.

Что если граф несвязный?

Пути нет, если рёбра лежат в двух компонентах. Изолированные вершины без рёбер не мешают.