Алгоритм Хирхольцера: как найти эйлеров путь

Алгоритм Хирхольцера строит маршрут, который проходит по каждому ребру графа ровно один раз. Вершины при этом могут повторяться: важно не путать повторное посещение перекрёстка с повторным проходом по дороге. Такой маршрут называют эйлеровым путём, а если он заканчивается в начальной вершине - эйлеровым циклом. Ниже разберём условия существования, сборку маршрута и реализацию через стек. На схеме можно самостоятельно проследить выбор рёбер и порядок записи вершин.
Как два цикла становятся одним маршрутом
Представьте две треугольные дорожки с общей вершиной А. Можно начать в А, обойти первый треугольник и вернуться в А. Но часть рёбер ещё не пройдена: второй треугольник можно вставить в маршрут в том месте, где уже встретилась А. Получится один замкнутый обход всех шести рёбер.
Именно это объединение циклов лежит в основе метода. Он решает задачу прохода по рёбрам, а не задачу кратчайшего пути между двумя вершинами. Для последней при неотрицательных весах применяют, например, алгоритм Дейкстры. Задача Хирхольцера не требует минимизировать длину: каждое заданное ребро должно попасть в ответ ровно один раз.
Когда эйлеров путь существует
Для неориентированного графа с хотя бы одним ребром сначала отбросим из рассмотрения изолированные вершины: они не мешают пройти по рёбрам. Все остальные вершины должны лежать в одной компоненте связности. Затем считаем степени - количество инцидентных рёбер, причём петля даёт два вклада в степень своей вершины.
- Если все степени чётные, существует эйлеров цикл. Начать можно в любой вершине с ненулевой степенью.
- Если нечётных вершин ровно две, существует открытый эйлеров путь. Начало и конец обязательно находятся в этих двух вершинах.
- При другом числе нечётных вершин такого пути нет.
Причина чётности проста: в промежуточную вершину маршрут входит по одному ребру и выходит по другому. У открытого пути только начало и конец имеют по одному непарному входу или выходу. У замкнутого маршрута пары есть и в начальной вершине. Обратное утверждение тоже верно при указанной связности; его формулировку и доказательство можно найти в курсе теории графов Whitman College.
В графе без рёбер обычно отдельно выбирают соглашение: маршрут из одной вершины допустим как путь длины ноль, если вершина существует. Это граничный случай, а не повод запускать выбор рёбер. Саму связность удобно проверить обходом в ширину или в глубину, начиная с вершины ненулевой степени.
Пример: шесть рёбер и семь записей вершин
Возьмём рёбра АБ, БВ, ВА, АГ, ГД и ДА. У А степень 4, у Б, В, Г и Д - по 2. Все пять вершин связаны, все степени чётные, значит цикл существует. Один возможный ответ:

Здесь А встречается трижды, но это допустимо. Между семью соседними записями ровно шесть переходов, и каждый соответствует своему ребру. Можно обойти треугольники в другом порядке или в обратном направлении: единственность ответа не требуется. Для ручной проверки полезно вычеркнуть каждое ребро в исходном списке по мере чтения маршрута.
На рисунке нет кратных рёбер, но алгоритм работает и с ними. Если две дороги соединяют одну пару вершин, им нужны разные идентификаторы: отметка «пара АБ уже использована» ошибочно удалит обе. В списке смежности каждое неориентированное ребро хранится у обоих концов с одним и тем же идентификатором.
Открытый маршрут на другом примере
Уберём из исходного примера рёбра АГ, ГД и ДА, а затем оставим одно ребро АГ. Получится треугольник АБВА с хвостом АГ. Степени А и Г равны соответственно 3 и 1, остальные равны 2. Значит открытый путь должен соединять А и Г: например, А → Б → В → А → Г. Начинать в Б нельзя, хотя из неё можно пройти некоторые рёбра: корректный полный путь обязан иметь концами именно нечётные вершины.
На практике это различие полезно при планировании обхода дорог или линий, если требуется пройти каждый участок один раз. Модель сначала нужно построить аккуратно: перекрёстки представить вершинами, участки между ними - отдельными рёбрами, а ограничения направления учесть стрелками. Если повторные проходы разрешены или требуется минимальная стоимость, постановка уже отличается от задачи поиска эйлерова пути.
Стек и обратная сборка ответа
Вместо явного вырезания и вставки циклов удобно поддерживать стек текущего обхода. Его верхушка - текущая вершина. Пока у неё есть неиспользованное ребро, помечаем ребро и кладём другой его конец в стек. Когда свободных рёбер больше нет, снимаем вершину со стека и добавляем её в конец временного списка. В конце этот список нужно перевернуть.
Для примера выше при указанном порядке рёбер стек сначала растёт так: А; А, Б; А, Б, В; А, Б, В, А; затем добавляются Г, Д и А. После шестого перехода свободных рёбер нет. Вершины снимаются в порядке А, Д, Г, А, В, Б, А. Переворот даёт маршрут А, Б, В, А, Г, Д, А. Ползунок показывает и промежуточные состояния: частично перевёрнутый список ещё не обязан быть полным маршрутом.
Псевдокод для подходящей начальной вершины выглядит так:
стек = [s], ответ = []
пока стек не пуст:
v = верхушка стека
если у v есть неиспользованное ребро e = (v, u):
отметить e использованным
положить u в стек
иначе:
снять v со стека и добавить в ответ
перевернуть ответ
В отличие от обычного обхода в глубину, здесь нельзя просто пометить вершину посещённой и запретить возвращаться в неё. В стеке одна и та же вершина может встречаться несколько раз, а пометки относятся к рёбрам. При снятии вершина попадает в уже завершённый хвост маршрута; оставшиеся в стеке переходы присоединяются к этому хвосту раньше после переворота.
Почему метод не теряет рёбра
Рассмотрим сначала случай цикла. Если начать в вершине с ненулевой степенью и идти по свободным рёбрам, застрять вне начала нельзя: каждое прибытие в другую вершину оставляет парное свободное ребро для выхода. Первый замкнутый обход может использовать не всё. Но если неиспользованные рёбра остались, связность исходного графа гарантирует, что у некоторой вершины уже построенного обхода есть ещё свободное ребро.
Из этой вершины аналогично строится новый замкнутый обход; его можно вставить при очередном посещении общей вершины. Повторяем до исчерпания рёбер. Стек выполняет ту же сборку неявно: он откладывает окончательное положение вершины, пока из неё можно продолжать путь. Для открытого пути рассуждение можно свести к циклу, временно добавив ребро между двумя нечётными вершинами и затем разрезав цикл по этому ребру.
После выполнения полезно проверить, что выбраны все рёбер, а в результате записей вершин. Проверка длины дополняет проверку степеней и связности; одна только длина не заменяет корректной маркировки рёбер. Для полного контроля также сверяют каждую соседнюю пару с соответствующим уникальным ребром.
Ориентированный граф и стоимость
В ориентированном графе ребро можно проходить только по направлению стрелки. Для цикла у каждой вершины входящая и исходящая степени равны. Для открытого пути у начала исходящая степень на единицу больше входящей, у конца входящая на единицу больше исходящей, у остальных степени равны. Все вершины с ненулевой степенью должны быть связаны после игнорирования направлений. Выбирают соответствующее начало и при построении рассматривают только исходящие дуги.
При списках смежности и указателе текущей позиции для каждой вершины алгоритм работает за с учётом подготовки и проверки графа. Каждую запись смежности просматривают не более одного раза; повторный поиск с начала списка на каждом шаге может ухудшить оценку. Память обычной реализации вместе со списками, отметками, стеком и ответом - . Важно учитывать и сам маршрут: в нём вершин.
Частые ошибки
- Проверять только степени и забывать про отдельную компоненту с рёбрами: один маршрут не сможет пройти обе компоненты.
- Для открытого пути начинать в чётной вершине, а не в одной из двух нечётных.
- Помечать вершины вместо отдельных рёбер или считать два параллельных ребра одним.
- Забывать перевернуть список вершин после снятия со стека.
- Для ориентированного графа игнорировать направления дуг при построении маршрута.
FAQ
Чем эйлеров путь отличается от гамильтонова? Эйлеров проходит каждое ребро ровно раз и может повторять вершины. Гамильтонов путь посещает каждую вершину ровно раз; это другое условие.
Обязательно ли выбирать мост последним? В реализации Хирхольцера со стеком специальная проверка мостов не нужна: при корректном выборе начала обратная сборка соединяет пройденные участки.
Можно ли получить несколько правильных ответов? Да. Порядок выбора свободных рёбер влияет на маршрут, но любой полученный корректный ответ проходит все рёбра ровно по разу.
Коротко
Проверьте связность непустой части графа и степени, выберите допустимое начало, затем двигайтесь по неиспользованным рёбрам со стеком. Вершины без свободных выходов записывайте при снятии и переверните запись в конце. При корректном хранении рёбер метод строит эйлеров маршрут за линейное время.
Читайте также

Задача о мостах Кёнигсберга: степени графа и теорема Эйлера
Задача о семи мостах Кёнигсберга простыми словами: как построить граф из районов и мостов, что такое степень вершины и почему по теореме Эйлера обойти все мосты по одному разу нельзя.

Алгоритм Флойда-Уоршелла: кратчайшие пути в графе
Алгоритм Флойда-Уоршелла на примере: как получить матрицу кратчайших путей для всех пар вершин, восстановить маршрут и вовремя обнаружить отрицательный цикл.

Дерево: свойства и число рёбер
Как связаны вершины и рёбра дерева, почему их числа отличаются на единицу и какие признаки помогают отличить дерево от произвольного графа. Примеры и доказательство.

Формула Эйлера для планарных графов
Формула Эйлера для планарных графов: как считать вершины, рёбра и грани, почему учитывается внешняя область и как доказать равенство для связного графа.

Максимальный поток: алгоритм Форда-Фалкерсона
Максимальный поток алгоритмом Форда-Фалкерсона: разбираем остаточную сеть, обратные рёбра и дополняющие пути на примере, а результат проверяем разрезом.

Список смежности: представление графа с примерами
Как построить список смежности графа по рёбрам и восстановить граф по спискам. Разбираем ориентированные и взвешенные графы, сложность операций и отличие от матрицы.