Обходы графов: BFS, DFS, Эйлеровы и Гамильтоновы циклы

Курьеру нужно объехать все точки доставки, ревизору — проверить все счётчики в доме, программе — посетить каждую вершину дерева решений. Везде одна и та же математика: обход графа. Но «обойти» можно по-разному, и от способа зависит, что получится на выходе. Разберём два базовых обхода — в ширину и в глубину, а потом два знаменитых «специализированных» обхода: эйлеров и гамильтонов. Первый из них когда-то запустил всю теорию графов.

BFS и DFS: очередь против стека#

Обход в ширину (BFS) идёт слоями: сначала все соседи стартовой вершины, потом соседи соседей. Технически это очередь — кто раньше встал, тот раньше вышел. Обход в глубину (DFS), наоборот, забирается как можно дальше по одному маршруту, а упёршись, возвращается назад. Это стек — последний пришёл, первым ушёл. Оба обхода помечают посещённые вершины, чтобы не крутиться по кругу, и работают за $O(n+m)$: каждая вершина и каждое ребро обрабатываются постоянное число раз.

Зачем нужны оба? BFS обладает красивым свойством: найденное им дерево путей содержит кратчайшие маршруты (по числу рёбер) от старта до всех вершин. Поэтому BFS — основа поиска в невзвешенных графах: «на каком уровне соцсети находится человек». DFS силён в другом: поиск циклов, топологическая сортировка ориентированного графа, проверка двудольности, разрезание мостов. Порядки обхода одного и того же графа у них разные — потрогайте это на симуляторе.

Деревья обхода: что остаётся после прогулки

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

Практические применения стоит держать в голове списком. BFS: кратчайший маршрут в невзвешенном графе, проверка двудольности (красьте слои в два цвета), поиск всех вершин на расстоянии не больше $k$. DFS: топологическая сортировка, разбиение на компоненты, поиск мостов и точек сочленения, анализ потоков выполнения. Полезный факт про связность: один запуск любого обхода покрывает ровно одну компоненту связности — если после обхода остались непосещённые вершины, граф несвязен, и число таких «перезапусков» равно числу компонент.

Отдельно о топологической сортировке — любимом вопросе на собеседованиях. Задача: упорядочить вершины ориентированного графа так, чтобы каждое ребро вело от более ранней вершины к более поздней. Модель: порядок изучения предметов по пререквизитам или порядок сборки модулей по зависимостям. Решение через DFS: записывайте вершину в список после обработки всех исходящих рёбер, затем разверните список. Если в процессе обнаружилось обратное ребро — в графе цикл, и топологического порядка не существует: зависимости замкнулись в круг.

Ещё одна деталь, которую студенты замечают на симуляторе: порядок обхода зависит от порядка перебора соседей. Два корректных DFS одного графа дают разные последовательности — и оба «правильные». На экзамене это стоит оговаривать: без зафиксированного порядка соседей порядок посещения не единственный, а вот множества вершин каждой компоненты и факт связности — единственные.

Эйлеров цикл: обходим все рёбра#

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

• эйлеров цикл существует тогда и только тогда, когда все степени чётны
• эйлеров путь существует тогда и только тогда, когда ровно две вершины имеют нечётную степень (они и станут концами пути)

Почему это работает, видно из соображения «пришёл — ушёл»: заходя в вершину по одному ребру, маршрут обязан покинуть её по другому. Каждое посещение съедает пару рёбер — значит, степень каждой промежуточной вершины чётна. Для цикла это верно и у стартовой вершины, а для пути — везде, кроме его концов. Именно на таких соображениях Эйлер в 1736 году разобрал Кёнигсберг: четыре участка суши, семь мостов, степени $5,3,3,3$ — четыре нечётные вершины, и ни цикла, ни пути быть не может; определение замкнутого маршрута по рёбрам — в статье эйлеров цикл.

Гамильтонов цикл: обходим все вершины#

Гамильтонов цикл — маршрут по всем вершинам ровно по одному разу с возвратом в старт. Похоже на эйлеров, но с точностью до наоборот: там считаем рёбра, здесь вершины. И — сюрприз — красивого критерия «тогда и только тогда» для гамильтоновости нет. Задача «есть ли гамильтонов цикл» — классическая NP-полная задача: при больших графах проверка перебором непрактична, а полиномиального алгоритма никто не нашёл (и в общем случае его, скорее всего, не существует).

Что делать на практике? Пользоваться достаточными условиями. Самое известное — условие Дирака: если в графе с $n\ge 3$ вершинами степень каждой вершины не меньше $n/2$, гамильтонов цикл гарантирован. Логика интуитивная: чем «гуще» граф, тем меньше шансов, что какой-то маршрут застрянет в тупике.

Проверим условие Дирака на кубе: 8 вершин, каждая степень 3. Требование $\mathrm{deg}\ge 4$ не выполнено — Дирак молчит. Но гамильтонов цикл в кубе есть: обойдите вершины по большому кругу, задев каждую ровно раз. Мораль: достаточное условие не является необходимым — его невыполнение ничего не запрещает. Обратная сторона: если степени малы, искать цикл придётся честным перебором с отсечениями.

Самая известная родственница этой задачи — задача коммивояжёра: объехать все города, вернуться и потратить минимум топлива. Точная постановка NP-трудна, но на реальных данных отлично работают приближённые методы: жадный выбор ближайшего города, 2-оптимизация и эвристики на минимальных остовных деревьях, о которых пойдёт речь в уроке о деревьях.