BFS: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
Строка 61: Строка 61:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
 +
==Модификации и идеи==
 +
 +
===Кратчайшее расстояние между двумя вершинами===
 +
Предположим, нам надо найти кратчайший путь между двумя вершинами $u$ и $v$ в графе, в котором довольно много рёбер. Обычный BFS, запущенный из $u$ в худшем случае пройдёт все рёбра, прежде, чем найдёт $v$. Хочется попробовать ускорить процесс, ведь мы знаем, в какую вершину мы хотим попасть.
 +
 +
Для этого можно запустить BFS сразу из двух вершин, ведя его как бы параллельно, сначала обрабатывая вершины на расстоянии 1 от хотя бы одной из стартовых, затем на расстоянии 2 итд. Тогда первая вершина, до которой дойдут обе 'волны' и будет той, через которую будет проходить кратчайший путь.
 +
 +
Как это закодить? Надо просто вместо вершины, хранить пару -- (текущая вершина, стартовая вершина), а в начале алгоритма закинуть в очередь пары $(v, v)$ и $(u, u)$.
 +
 +
===Кратчайшее расстояние от всех вершин графа до выделенных===
 +
Идею с несколькими стартами в BFS можно применить для такой задачи:
 +
Вам дан граф с выделенным множеством вершин $S$. Вам надо для каждой вершины графа узнать ближайшую к ней из $S$ и найти до неё расстояние.
 +
 +
Решение: снова добавляем в очередь пары $(s_i, s_i)$ и итерируемся, пока есть хотя бы одна непосещённая вершина(это можно сделать, например, поддерживая счётчик вершин, которые мы посетили).
  
 
{{Автор|Глеб Лобанов|glebodin}}
 
{{Автор|Глеб Лобанов|glebodin}}

Версия 14:25, 16 ноября 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;
}

Модификации и идеи

Кратчайшее расстояние между двумя вершинами

Предположим, нам надо найти кратчайший путь между двумя вершинами $u$ и $v$ в графе, в котором довольно много рёбер. Обычный BFS, запущенный из $u$ в худшем случае пройдёт все рёбра, прежде, чем найдёт $v$. Хочется попробовать ускорить процесс, ведь мы знаем, в какую вершину мы хотим попасть.

Для этого можно запустить BFS сразу из двух вершин, ведя его как бы параллельно, сначала обрабатывая вершины на расстоянии 1 от хотя бы одной из стартовых, затем на расстоянии 2 итд. Тогда первая вершина, до которой дойдут обе 'волны' и будет той, через которую будет проходить кратчайший путь.

Как это закодить? Надо просто вместо вершины, хранить пару -- (текущая вершина, стартовая вершина), а в начале алгоритма закинуть в очередь пары $(v, v)$ и $(u, u)$.

Кратчайшее расстояние от всех вершин графа до выделенных

Идею с несколькими стартами в BFS можно применить для такой задачи: Вам дан граф с выделенным множеством вершин $S$. Вам надо для каждой вершины графа узнать ближайшую к ней из $S$ и найти до неё расстояние.

Решение: снова добавляем в очередь пары $(s_i, s_i)$ и итерируемся, пока есть хотя бы одна непосещённая вершина(это можно сделать, например, поддерживая счётчик вершин, которые мы посетили).



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin