Обход в ширину

Очередь вместо стека — и обход начинает выдавать кратчайшие расстояния. Почему это работает, как восстановить путь и что ломается, если помечать вершину не в тот момент.

8 мин

Обход в глубину уходит по первому попавшемуся ребру как можно дальше. Обход в ширину поступает наоборот: он полностью разбирается с ближайшими вершинами, потом с теми, что на расстоянии два, и так далее.

Разница в коде — одна структура данных. Вместо стека очередь.

vector<int> bfs(int start) {
    vector<int> dist(n + 1, -1);
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int to : g[v])
            if (dist[to] == -1) {          // ещё не видели
                dist[to] = dist[v] + 1;    // помечаем здесь, при добавлении
                q.push(to);
            }
    }
    return dist;
}

Массив dist работает сразу за двоих: он и хранит расстояния, и заменяет visited — значение $-1$ означает «не посещали».

Результат: dist[v] — длина кратчайшего пути из start в v, а $-1$ — «недостижима». Обход в глубину такого не даёт, и это главное, ради чего его меняют на обход в ширину.

Почему получаются именно кратчайшие пути

Ключевое наблюдение: расстояния в очереди не убывают, и в ней одновременно лежат вершины не более чем двух соседних слоёв.

Докажем индукцией по числу шагов. В начале в очереди одна вершина с расстоянием $0$ — условие выполнено. Пусть перед очередным шагом в очереди лежат вершины с расстояниями $d$ и $d+1$ , именно в таком порядке. Мы снимаем вершину с расстоянием $d$ и добавляем в конец её непосещённых соседей со значением $d+1$ . Значит, в очереди по-прежнему сначала $d$ , потом $d+1$ . Когда все вершины со значением $d$ кончились, впереди $d+1$ , и всё повторяется на единицу выше.

Отсюда следует главное. Пусть настоящее кратчайшее расстояние до $v$ равно $k$ , и путь до неё идёт через вершину $u$ с расстоянием $k-1$ . По индукции $u$ получила правильное значение $k-1$ и когда-то была снята с очереди. В этот момент $v$ либо уже имела значение — и оно было не больше $k$ , потому что вершины снимаются в порядке возрастания расстояния, — либо получила ровно $k$ . Меньше $k$ она получить не могла: значение $j < k$ означало бы путь длины $j$ , а $k$ — кратчайшее.

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

Сколько это стоит

Каждая вершина кладётся в очередь ровно один раз, каждое ребро просматривается по разу с каждого конца. Итого $O(n + m)$ — та же оценка, что у обхода в глубину.

Замер: граф на $10^5$ вершинах и $2 \cdot 10^5$ рёбрах обходится за 4 мс (400 000 просмотров рёбер). Сетка $1000 \times 1000$ с двадцатью процентами стен — за 19 мс. То есть обход в ширину практически бесплатен, и упираться в лимит вы будете не в нём.

Где именно ставится пометка

Это самая частая ошибка, и коварна она тем, что ответ остаётся правильным.

while (!q.empty()) {
    int v = q.front(); q.pop();
    if (done[v]) continue;              // ПЛОХО: помечаем при снятии
    done[v] = true;
    for (int to : g[v]) if (!done[to]) q.push(to);
}

Расстояния такой код посчитает верно. Но одна и та же вершина попадёт в очередь столько раз, сколько у неё соседей, и размер очереди становится $O(m)$ вместо $O(n)$ .

Замер на полном графе $K_n$ :

$n$	при добавлении	при снятии
1000	999 добавлений, 0.4 мс	499 500 добавлений, 1.6 мс
2000	1999 добавлений, 1.8 мс	1 999 000 добавлений, 7.0 мс
4000	3999 добавлений, 7.2 мс	7 998 000 добавлений, 27.8 мс

Асимптотика по времени не портится — она и так $O(m)$ , — а вот память растёт с $O(n)$ до $O(m)$ , и на графе с $10^6$ рёбер очередь весит несколько мегабайт вместо нескольких сотен килобайт. Плюс четырёхкратное замедление на ровном месте.

Правило простое: помечать вершину в тот момент, когда кладёте её в очередь.

Восстановление пути

Расстояние — это половина ответа; часто просят сам путь. Два способа.

Массив предков. При посещении запоминаем, откуда пришли, потом идём назад от финиша:

if (dist[to] == -1) { dist[to] = dist[v] + 1; parent[to] = v; q.push(to); }

Спуск по расстояниям. Массива предков не нужно вовсе: стоя в вершине $v$ , ищем любого соседа с dist на единицу меньше и переходим в него. Такой сосед всегда есть, если вершина достижима.

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

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

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

Несколько источников

Задача: на карте несколько пожаров, для каждой клетки нужно расстояние до ближайшего. Наивно — запустить обход из каждого пожара и взять минимум, это $O(k(n+m))$ .

Правильно — положить в очередь сразу все источники с расстоянием ноль:

for (int s : sources) { dist[s] = 0; q.push(s); }

Дальше всё без изменений, и стоит это те же $O(n + m)$ . Формально это обход из одной фиктивной вершины, соединённой рёбрами нулевого веса со всеми источниками; но добавлять её в граф не нужно, достаточно заполнить очередь.

Если помимо расстояния нужен и номер ближайшего источника, его протаскивают вместе с расстоянием: source[to] = source[v]. При равных расстояниях ответов несколько, и условие обычно требует наименьший номер — тогда придётся ещё и подправлять уже посчитанные вершины на том же слое.

Что ещё считается тем же обходом

Число кратчайших путей. Сначала обходом считаем расстояния, потом перебираем вершины в порядке возрастания dist и складываем: $\mathrm{ways}[v] = \sum \mathrm{ways}[u]$ по соседям $u$ с $\mathrm{dist}[u] = \mathrm{dist}[v] - 1$ . Порядок обхода уже отсортирован по расстоянию, так что отдельная сортировка не нужна.

Рёбра, лежащие на каком-нибудь кратчайшем пути. Запускаем обход из старта и из финиша. Ребро $(u, v)$ лежит на кратчайшем пути тогда и только тогда, когда $\mathrm{from}[u] + 1 + \mathrm{to}[v]$ равно длине кратчайшего пути (или то же самое с переставленными концами).

Диаметр дерева. Два обхода: из произвольной вершины — до самой далёкой, из неё — снова до самой далёкой. Подробности и доказательство — в статье «Диаметр дерева».

Размеры слоёв, проверка двудольности, компоненты связности — всё это обход в ширину умеет ровно так же, как обход в глубину. Выбор между ними определяется одним вопросом: нужны ли кратчайшие расстояния.

Когда обход в ширину не подходит

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

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

Смежное

Обход в глубину — что даёт стек вместо очереди;
Неявный граф — карты, доски и всё, где вершины считаются на месте;
Граф состояний — когда вершина это не точка, а положение дел;
Дерево кратчайших путей — структура, которую обход строит попутно.