BFS: различия между версиями
Глеб (обсуждение | вклад) |
|||
Строка 63: | Строка 63: | ||
==Модификации и идеи== | ==Модификации и идеи== | ||
− | + | *[[Кратчайшее расстояние между двумя вершинами]] | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
===Кратчайшее расстояние от всех вершин графа до выделенных=== | ===Кратчайшее расстояние от всех вершин графа до выделенных=== | ||
Идею с несколькими стартами в BFS можно применить для такой задачи: | Идею с несколькими стартами в BFS можно применить для такой задачи: | ||
Строка 75: | Строка 69: | ||
Решение: снова добавляем в очередь пары $(s_i, s_i)$ и итерируемся, пока есть хотя бы одна непосещённая вершина(это можно сделать, например, поддерживая счётчик вершин, которые мы посетили). | Решение: снова добавляем в очередь пары $(s_i, s_i)$ и итерируемся, пока есть хотя бы одна непосещённая вершина(это можно сделать, например, поддерживая счётчик вершин, которые мы посетили). | ||
+ | |||
+ | *[[0-1 BFS]] | ||
+ | *[[1-k BFS]] | ||
{{Автор|Глеб Лобанов|glebodin}} | {{Автор|Глеб Лобанов|glebodin}} | ||
{{Автор|Александр Гришутин|rationalex}} | {{Автор|Александр Гришутин|rationalex}} |
Версия 22:41, 18 ноября 2019
Содержание
BFS
BFS — breadth-first search, или же поиск в ширину.
Алгоритм
Алгоритм работает следующим образом.
1. Создадим массив $dist$ расстояний. Изначально $dist[s] = 0$ (поскольку расстояний от вершины до самой себя равно $0$) и $dist[v] = \infty$ для $v \neq s$.
2. Создадим очередь $q$. Изначально в $q$ добавим вершину $s$.
3. Пока очередь $q$ непуста, делаем следующее:
a) Извлекаем вершину $v$ из очереди.
b) Рассматриваем все рёбра $(v, u) \in E$. Для каждого такого ребра пытаемся сделать релаксацию: если $dist[v] + 1 < dist[u]$, то мы делаем присвоение $dist[u] = dist[v] + 1$ и добавляем вершину $u$ в очередь.
Визуализации:
Интуитивное понимание алгоритма
Можно представить, что мы поджигаем вершину $s$. Каждый шаг алгоритма — это распространение огня на соседние вершины. Понятно, что огонь доберётся до вершины по кратчайшему пути.
Заметьте, что этот алгоритм очень похож на DFS — достаточно заменить очередь на стек и поиск в ширину станет поиском в глубину. Действительно, оба алгоритма при обработке вершины просто записывают всех непосещенных соседей, в которые из неё есть ребро, в структуру данных, и после этого выбирает следующую вершину для обработки в структуре данных. В DFS это стек (благодаря рекурсии), поэтому мы сначала записываем соседа, идем в обрабатываем его полностью, а потом начинаем обрабатывать следующего соседа. В BFS это очередь, поэтому мы кидаем сразу всех соседей, а потом начинаем обрабатывать вообще другую вершину - ту непосещенную, которую мы положили в очередь раньше всего.
Оба алгоритма позволяют обойти граф целиком - посетить каждую вершину ровно один раз. Поэтому они оба подходят для таких задач как:
- поиск компонент связности
- проверка графа на двудольность
- построение остова
Реализация
vector<int> bfs(int s) {
// длина любого кратчайшего пути не превосходит n - 1,
// поэтому n - достаточное значение для "бесконечности";
// после работы алгоритма dist[v] = n, если v недостижима из s
vector<int> dist(n, n);
dist[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int u : adj[v]) {
if (dist[u] > dist[v] + 1) {
dist[u] = dist[v] + 1;
q.push(u);
}
}
}
return dist;
}
Модификации и идеи
Кратчайшее расстояние от всех вершин графа до выделенных
Идею с несколькими стартами в BFS можно применить для такой задачи: Вам дан граф с выделенным множеством вершин $S$. Вам надо для каждой вершины графа узнать ближайшую к ней из $S$ и найти до неё расстояние.
Решение: снова добавляем в очередь пары $(s_i, s_i)$ и итерируемся, пока есть хотя бы одна непосещённая вершина(это можно сделать, например, поддерживая счётчик вершин, которые мы посетили).
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin
Автор конспекта: Александр Гришутин
По всем вопросам пишите в telegram @rationalex