Поиск в ширину (англ. breadth-first search) — один из основных алгоритмов на графах, позволяющий находить все кратчайшие пути от заданной вершины и решать многие другие задачи.
Поиск в ширину также называют обходом — так же, как поиск в глубину и все другие обходы, он посещает все вершины графа по одному разу, только в другом порядке: по увеличению расстояния до начальной вершины.
#Описание алгоритма
На вход алгоритма подаётся невзвешенный граф и номер стартовой вершины $s$. Граф может быть как ориентированным, так и неориентированным — для алгоритма это не важно.
Основную идею алгоритма можно понимать как процесс «поджигания» графа: на нулевом шаге мы поджигаем вершину $s$, а на каждом следующем шаге огонь с каждой уже горящей вершины перекидывается на всех её соседей, в конечном счете поджигая весь граф.
Если моделировать этот процесс, то за каждую итерацию алгоритма будет происходить расширение «кольца огня» в ширину на единицу. Номер шага, на котором вершина $v$ начинает гореть, в точности равен длине её минимального пути из вершины $s$.
Моделировать это можно следующим образом. Создадим очередь, в которую будут помещаться горящие вершины, а также заведём булевый массив, в котором для каждой вершины будем отмечать, горит она или нет — или иными словами, была ли она уже посещена. Изначально в очередь помещается только вершина $s$, которая сразу помечается горящей.
Затем алгоритм представляет собой такой цикл: пока очередь не пуста, достать из её головы одну вершину $v$, просмотреть все рёбра, исходящие из этой вершины, и если какие-то из смежных вершин $u$ ещё не горят, поджечь их и поместить в конец очереди.
В итоге, когда очередь опустеет, мы по одному разу обойдём все достижимые из $s$ вершины, причём до каждой дойдём кратчайшим путём. Длины кратчайших путей можно посчитать, если завести для них отдельный массив $d$ и при добавлении в очередь пересчитывать по правилу $d_u = d_v + 1$. Также можно компактно сохранить дополнительную информацию для восстановления самих путей, заведя массив «предков», в котором для каждой вершины хранится номер вершины из которой мы в неё попали.
#Реализация
Если мы всё равно поддерживаем массив расстояний, то отдельный булевый массив с метками горящих вершин можно не создавать, а вместо этого просто присвоить изначальное расстояние всех вершин некоторым некоторым специальным значением (например, -1), которое будет сигнализировать а том, что эту вершину мы ещё не просмотрели.
vector<int> g[maxn];
void bfs(int s) {
queue<int> q;
q.push(s);
vector<int> d(n, -1), p(n);
d[s] = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
for (int u : g[v]) {
if (d[u] == -1) {
q.push(u);
d[u] = d[v] + 1;
p[u] = v;
}
}
}
}
Теперь, чтобы восстановить кратчайший путь до какой-то вершины $v$, это можно сделать через массив p:
while (v != s) {
cout << v << endl;
v = p[v];
}
Обратим внимание, что путь выведется в обратном порядке.
#В неявных графах
Поиск в ширину часто применяется для поиска кратчайшего пути в неявно заданных графах.
В качестве конкретного примера, пусть у нас есть булева матрица размера $n \times n$, в которой помечено, свободна ли клетка с координатами $(x, y)$, и требуется найти кратчайший путь от $(x_s, y_t)$ до $(x_y, y_t)$ при условии, что за один шаг можно перемещаться в свободную соседнюю по вертикали или горизонтали клетку.
Можно сконвертировать граф в явный формат: как-нибудь пронумеровать все ячейки (например по формуле $x \cdot n + y$) и для каждой посмотреть на всех её соседей, добавляя ребро в $(x \pm 1, y \pm 1)$, если соответствующая клетка свободна.
Такой подход будет работать за оптимальное линейное время, однако с точки зрения реализации проще адаптировать не входные данные, а сам алгоритм обхода в глубину:
bool a[N][N]; // свободна ли клетка (x, y)
int d[N][N]; // кратчайшее расстояние до (x, y)
// чтобы немного упростить код
struct cell {
int x, y;
};
void bfs(cell s, cell t) {
queue<cell> q;
q.push(s);
memset(d, -1, sizeof d);
d[s.x][x.y] = 0;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
// просматриваем всех соседей
for (auto [dx, dy] : {{-1, 0}, {+1, 0}, {0, -1}, {0, +1}}) {
// считаем координаты соседа
int _x = x + dx, _y = y + dy;
// и проверяем, что он свободен и не был посещен ранее
if (a[_x][_y] && d[_x][_y] == -1) {
d[_x][_y] = d[x][y] + 1;
q.push_back({_x, _y});
}
}
}
}
Перед запуском bfs следует убедиться, что не произойдет выход за пределы границ. Вместо того, чтобы добавлять проверки на _x < 0 || x >= n и т. п. при просмотре возможных соседей, удобно сделать следующий трюк: изначально создать матрицу a с размерностями на 2 больше, чем нужно, и на этапе чтения данных заполнять её в индексации не с нуля, а с единицы. Тогда границы матрицы всегда будут заполнены нулями (то есть помечены непроходимыми) и алгоритм никогда в них не зайдет.
#Применения и обобщения
Помимо нахождения расстояний в невзвешенном графе, обход в ширину можно использовать для многих задач, в которых работает обход в глубину, например для поиска компонент связности или проверки на двудольность.
Множественный BFS. Добавив в очередь изначально не одну, а несколько вершин, мы найдем для каждой вершины кратчайшее расстояние до одной из них.
Это полезно для задач, в которых нужно моделировать пожар, наводнение, извержение вулкана или подобные явления, в которых источник «волны» не один. Также так можно чуть быстрее находить кратчайший путь для конкретной пары вершин, запустив параллельно два обхода от каждой и остановив в тот момент, когда они встретятся.
Игры. С помощью BFS можно найти решение какой-либо задачи / игры за наименьшее число ходов, если каждое состояние системы можно представить вершиной графа, а переходы из одного состояния в другое — рёбрами графа.
В качестве (нетривиального) примера: собрать кубик Рубика за наименьшее число ходов.
Кратчайшие циклы. Чтобы найти кратчайший цикл в ориентированном невзвешенном графе, можно произвести поиск в ширину из каждой вершины. Как только в процессе обхода мы пытаемся пойти из текущей вершины по какому-то ребру в уже посещённую вершину, то это означает, что мы нашли кратчайший цикл для данной вершины, и останавливаем обход. Среди всех таких найденных циклов (по одному от каждого запуска обхода) выбираем кратчайший.
Такой алгоритм будет работать за $O(n^2)$: худшим случаем будет один большой цикл, в котором мы для каждой вершины пройдемся по всем остальным.
Ребра на кратчайшем пути. Мы можем за линейное время найти все рёбра, лежащие на каком-либо кратчайшем пути между заданной парой вершин $a$ и $b$. Для этого нужно запустить два поиска в ширину: из $a$ и из $b$.
Обозначим через $d_a$ и $d_b$ массивы кратчайших расстояний, получившиеся в результате этих обходов. Тогда каждое ребро $(u,v)$ можно проверить критерием
$$ d_a[u] + d_b[v] + 1 = d_a[b] $$Альтернативно, можно запустить один обход из $a$, и когда он дойдет до $b$, начать рекурсивно проходиться по всем обратным ребрам, ведущим в более близкие к $a$ вершины (то есть те, для которых $d[u] = d[v] - 1$), отдельно помечая их.
Аналогично можно найти все вершины на каком-либо кратчайшем пути.
0-1 BFS. Если веса некоторых ребер могут быть нулевыми, то кратчайшие пути искать не сильно сложнее.
Ключевое наблюдение: если от вершины $a$ до вершины $b$ можно дойти по пути, состоящему из нулевых рёбер, то кратчайшие расстояния от вершины $s$ до этих вершин совпадают.
Если в нашем графе оставить только $0$-рёбра, то он распадётся на компоненты связности, в каждой из которых ответ одинаковый. Если теперь вернуть единичные рёбра и сказать, что эти рёбра соединяют не вершины, а компоненты связности, то мы сведём задачу к обычному BFS.
Получается, запустив обход, мы можем при обработке вершины $v$, у которой есть нулевые ребра в непосещенные вершины, сразу пройтись по ним и добавить все вершины нулевой компоненты, проставив им такое же расстояние, как и у $v$.
Это можно сделать и напрямую, запустив BFS внутри BFS, однако можно заметить, что достаточно при посещении вершины просто добавлять всех её непосещенных соседей по нулевым ребрам в голову очереди, чтобы обработать их раньше, чем те, которые там уже есть. Это легко сделать, если очередь заменить деком:
vector<int> d(n, -1);
d[s] = 0;
deque<int> q;
q.push_back(s);
while (!q.empty()) {
int v = q.front();
q.pop_front();
for (auto [u, w] : g[v]) {
if (d[u] == -1) {
d[u] = d[v] + w;
if (w == 0)
q.push_front(u);
else
q.push_back(u);
}
}
}
Также вместо дека можно завести две очереди: одну для нулевых ребер, а другую для единичных, в внутри цикла while сначала просматривать первую, а только потом, когда она станет пустой, вторую. Этот подход уже можно обобщить.
1-k BFS. Теперь веса рёбер принимают значения от $1$ до некоторого небольшого $k$, и всё так же требуется найти кратчайшие расстояния от вершины $s$, но уже в плане суммарного веса.
Наблюдение: максимальное кратчайшее расстояние в графе равно $(n - 1) \cdot k$.
Заведём для каждого расстояния $d$ очередь $q_d$, в которой будут храниться вершины, находящиеся на расстоянии $d$ от $s$ — плюс, возможно, некоторые вершины, до которых мы уже нашли путь длины $d$ от $s$, но для которых возможно существует более короткий путь. Нам потребуется $O((n - 1) \cdot k)$ очередей.
Положим изначально вершину $s$ в $q_0$, а дальше будем брать вершину из наименьшего непустого списка и класть всех её непосещенных соседей в очередь с номером $d_v + w$ и релаксировать $d_u$, не забывая при этом, что кратчайшее расстояние до неё на самом деле может быть и меньше.
int d[maxn];
d[s] = 0;
queue<int> q[maxd];
q[0].push_back(s);
for (int dist = 0; dist < maxd; dist++) {
while (!q[dist].empty()) {
int v = q[dist].front();
q[dist].pop();
// если расстояние меньше и мы уже рассмотрели эту вершину,
// но она всё ещё лежит в более верхней очереди
if (d[v] > dist)
continue;
for (auto [u, w] : g[v]) {
if (d[u] < d[v] + w) {
d[u] = d[v] + w;
q[d[u]].push(u);
}
}
}
}
Сложность такого алгоритма будет $O(k n + m)$, поскольку каждую вершину мы можем прорелаксировать и добавить в другую очередь не более $k$ раз, а просматривать рёбра, исходящие из вершины мы будем только когда обработаем эту вершину в самый первый раз.
На самом деле, нам так много списков не нужно. Если каждое ребро имеет вес не более $k$, то в любой момент времени не более $k$ очередей будут непустыми. Мы можем завести только $k$ списков, и вместо добавления в $(d_v + w)$-ый список использовать $(d_v+w) \bmod k$.
Заметим, что алгоритм также работает когда есть общее ограничение на длину пути, а не только на вес каждого ребра. Для более общего случая, когда веса ребер могут быть любыми неотрицательными, есть алгоритм Дейкстры, который мы разберем в следующей статье.