Обход графа в ширину: очередь, слои и кратчайший путь

Обход графа в ширину (BFS, breadth-first search) - базовый способ систематически посетить все вершины, до которых можно добраться из заданной. Его идея в одной фразе: сначала осматриваем всех соседей старта, потом соседей соседей, и так далее, расходясь от начальной вершины ровной волной. Волну держит обычная очередь, а побочный эффект такого порядка оказывается важнее самого обхода: номер слоя, в котором вершина оказалась, и есть кратчайшее расстояние до неё в невзвешенном графе. Ниже разберём порядок посещения, восстановление пути, проверку двудольности и сложность $O(V + E)$. А для начала прокрутите обход по шагам в калькуляторе: он показывает, что лежит в очереди на каждом шаге и как растут расстояния.

Что такое обход графа в ширину

Пусть граф задан списками смежности, а обход стартует из вершины $s$. Обход в ширину строит слои:

$L_0 = \{s\}, \qquad L_{k+1} = \{\, v \notin L_0 \cup \dots \cup L_k : v \text{ смежна с какой-то вершиной из } L_k \,\}.$

Слой $L_k$ - это множество вершин, до которых от старта ровно $k$ рёбер. На учебном графе из калькулятора (8 вершин, 10 рёбер) обход из $A$ даёт слои $\{A\}$, $\{B, C, D\}$, $\{E, F\}$, $\{G\}$, $\{H\}$: сначала три прямых соседа старта, затем то, что видно с них, и так до самой дальней вершины $H$ на расстоянии 4.

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

Очередь и порядок посещения

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

d[s] ← 0;  p[s] ← нет;  очередь ← [s]
пока очередь не пуста:
    u ← извлечь из начала очереди
    для каждого соседа v вершины u:
        если d[v] ещё не определено:
            d[v] ← d[u] + 1
            p[v] ← u
            добавить v в конец очереди

Здесь $d[v]$ - расстояние от старта в рёбрах, $p[v]$ - вершина, из которой $v$ открыли. Массив $p$ пригодится дальше для восстановления пути.

Рассчитать для своей задачи

На нашем графе порядок выхода из очереди получается $A$, $B$, $C$, $D$, $E$, $F$, $G$, $H$. Обратите внимание: когда обрабатывается $C$, вершина $E$ уже открыта из $B$, поэтому ребро $C - E$ ничего не открывает. Таких рёбер здесь три: $C - E$, $D - F$, $F - G$. Остальные семь образуют дерево обхода, и это не случайность: каждое ребро дерева открывает ровно одну новую вершину, а новых вершин на единицу меньше, чем всего, значит в дереве обхода связного графа всегда $V - 1$ ребро.

Кратчайший путь в невзвешенном графе

Главное свойство обхода в ширину формулируется так: если все рёбра равноценны (вес каждого равен 1), то найденное значение $d[v]$ равно минимальному числу рёбер в пути от $s$ до $v$.

Почему так. Во-первых, $d[v]$ не может быть меньше истинного расстояния: значения выставляются вдоль рёбер по цепочке, то есть $d[v]$ - длина какого-то реального пути. Во-вторых, оно не может быть и больше. Пусть кратчайший путь до $v$ проходит через вершину $u$, для которой утверждение уже доказано. Вершина $u$ выходит из очереди раньше, чем любая вершина со строго большим расстоянием, и в этот момент $v$ либо уже открыта с расстоянием не больше $d[u] + 1$, либо открывается прямо сейчас именно с этим значением. Отсюда же следует полезное следствие: для любого ребра $(u, v)$ выполняется $|d[u] - d[v]| \le 1$, то есть ребро не может перепрыгнуть через слой.

Рассчитать для своей задачи

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

Восстановление пути по массиву предков

Сами расстояния отвечают на вопрос «сколько», а маршрут хранится в массиве предков $p$. Чтобы получить путь до вершины $t$, идут от неё назад: $t$, $p[t]$, $p[p[t]]$ и так до старта, у которого предка нет, а затем разворачивают последовательность.

Для нашего графа: $p[H] = G$, $p[G] = E$, $p[E] = B$, $p[B] = A$. Разворачиваем и получаем путь $A - B - E - G - H$ длиной 4 ребра - ровно столько, сколько обещало значение $d[H] = 4$. Кратчайший путь не обязан быть единственным: через $C$ и $F$ до $H$ ведёт путь той же длины, просто обход открыл $E$ первым. Хранить в очереди сами пути целиком не нужно и вредно: массив предков занимает $O(V)$ памяти вместо $O(V^2)$.

Проверка двудольности одним обходом

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

На учебном графе все десять рёбер идут между соседними слоями, доли получаются $\{A, E, F, H\}$ и $\{B, C, D, G\}$. Включите в калькуляторе ребро $B - C$: оба его конца лежат в слое 1, появляется треугольник $A - B - C$, и проверка честно сообщает, что двудольность сломалась. Сама двудольность нужна дальше для паросочетаний, например в теореме Кёнига.

Сложность обхода: O(V + E)

Каждая вершина попадает в очередь не больше одного раза, значит извлечений будет не больше $V$. Для извлечённой вершины просматривается её список смежности, то есть каждое ребро неориентированного графа рассматривается дважды, по разу с каждого конца. Итого

$T = O(V + E), \qquad M = O(V),$

и на нашем графе это $8 + 10 = 18$ элементарных шагов. Линейность держится только на списках смежности: если граф хранится матрицей, на каждую вершину уходит $O(V)$ проверок и обход вырождается в $O(V^2)$. Отсюда же стоимость производных задач: чтобы получить матрицу кратчайших расстояний или радиус и диаметр графа, запускают обход из каждой вершины и платят $O(V \cdot (V + E))$.

Чем обход в ширину отличается от обхода в глубину

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

Рассчитать для своей задачи

Обход в ширину выдаёт вершины по слоям и даёт кратчайший путь до каждой из них. Обход в глубину уходит по первой попавшейся ветке до упора: на том же графе он доберётся до $H$ маршрутом из 6 рёбер, хотя есть путь из 4. Поэтому, когда в задаче есть слово «кратчайший», а веса рёбер одинаковы, берут именно обход в ширину. По времени оба обхода одинаковы, $O(V + E)$, но по памяти в ширину дороже: очередь может разом хранить целый слой, то есть до $O(V)$ вершин, тогда как стек в глубину хранит лишь текущую ветку. На ациклическом графе очередь из этого же обхода работает ещё в одной классической задаче - топологической сортировке, где в неё кладут вершины с нулевой степенью входа.

Частые ошибки

• Помечать вершину при извлечении из очереди, а не при добавлении. Тогда вершина попадает в очередь столько раз, сколько у неё соседей в предыдущем слое, и время обхода растёт.
• Брать стек вместо очереди. Получится обход в глубину, а найденные расстояния перестанут быть кратчайшими.
• Применять обход в ширину к взвешенному графу. При разных весах первая встреча с вершиной не гарантирует минимальную стоимость, нужен Дейкстра.
• Обходить только из одной вершины и считать, что граф пройден. В несвязном графе обход накрывает лишь одну компоненту, остальные надо запускать отдельно.
• Класть в очередь сами пути вместо вершин. Память раздувается до $O(V^2)$, хотя достаточно массива предков.

FAQ

Обход в ширину и поиск в ширину - это одно и то же? Да, это два русских названия одного алгоритма BFS. Слово «поиск» подчёркивает задачу найти конкретную вершину, слово «обход» - задачу посетить все достижимые, но сам порядок действий совпадает.

Работает ли обход в ширину на ориентированном графе? Работает: из извлечённой вершины идут только по исходящим дугам. Расстояния при этом несимметричны, и из $u$ в $v$ может быть путь, а обратно нет, поэтому недостижимые вершины так и остаются с неопределённым $d$.

Как обойти весь граф и посчитать компоненты связности? Перебирают вершины подряд и из каждой непосещённой запускают новый обход, увеличивая счётчик. Суммарная сложность остаётся $O(V + E)$: каждая вершина и каждое ребро обрабатываются один раз за все запуски.

Коротко

Обход графа в ширину раскладывает вершины по слоям расстояния от старта: очередь выдаёт их в порядке неубывания $d$, вершина помечается при добавлении в очередь, а открывшее её ребро запоминается в массиве предков. В невзвешенном графе номер слоя равен кратчайшему расстоянию, а разворот массива предков даёт сам путь; той же волной проверяется двудольность по чётности слоя. Обход стоит $O(V + E)$ времени и $O(V)$ памяти на списках смежности, но вырождается в $O(V^2)$ на матрице смежности; для разных весов рёбер вместо него берут алгоритм Дейкстры.