BFS | kz-maxx

Объяснение

BFS — это обход графа в ширину. Полное название: Breadth-First Search.

BFS идет по графу слоями:

сначала стартовая вершина
потом все вершины на расстоянии 1
потом все вершины на расстоянии 2
потом все вершины на расстоянии 3

BFS использует queue, то есть обычную очередь.

queue<int> q;

BFS хорошо подходит для поиска кратчайшего пути в невзвешенном графе. Невзвешенный граф — это граф, где все ребра имеют одинаковую цену.

Главная идея BFS

В BFS мы храним:

Массив	Что хранит
g[v]	список соседей вершины v
used[v]	были ли мы уже в вершине v
dist[v]	расстояние от старта до вершины v
p[v]	родитель вершины v для восстановления пути

Алгоритм:

1. кладем стартовую вершину в очередь
2. достаем вершину из очереди
3. смотрим всех ее соседей
4. если сосед еще не посещен, добавляем его в очередь
5. повторяем, пока очередь не пустая

Пример обхода

Пусть есть граф:

1 -- 2 -- 4
|....|
3 -- 5

Стартуем из вершины 1.

dist[1] = 0
соседи 1: 2, 3
dist[2] = 1
dist[3] = 1

Потом BFS идет дальше.

из 2 можно попасть в 4 и 5
dist[4] = 2
dist[5] = 2

Итоговые расстояния:

Вершина	Расстояние от 1
1	0
2	1
3	1
4	2
5	2

Обычный BFS

Это базовая функция BFS.

void bfs(int start) {
    queue<int> q;

    used[start] = true;
    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int to : g[v]) {
            if (!used[to]) {
                used[to] = true;
                dist[to] = dist[v] + 1;
                p[to] = v;
                q.push(to);
            }
        }
    }
}

Здесь:

start — начальная вершина
q — очередь
used[to] проверяет, были ли мы в соседней вершине
dist[to] считает расстояние
p[to] запоминает родителя

Задача 1: расстояния от одной вершины

Дан невзвешенный неориентированный граф. Нужно найти расстояния от вершины s до всех остальных вершин.

Input

Output

0 1 1 2 2

В первой строке:

n = 5 — количество вершин
m = 5 — количество ребер
s = 1 — стартовая вершина

Полная реализация BFS

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m, s;
vector<int> g[N];
bool used[N];
int dist[N];
int p[N];

void bfs(int start) {
    queue<int> q;

    used[start] = true;
    dist[start] = 0;
    p[start] = -1;
    q.push(start);

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int to : g[v]) {
            if (!used[to]) {
                used[to] = true;
                dist[to] = dist[v] + 1;
                p[to] = v;
                q.push(to);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> s;

    for (int i = 1; i <= n; i++) {
        dist[i] = -1;
        p[i] = -1;
    }

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    bfs(s);

    for (int i = 1; i <= n; i++) {
        cout << dist[i] << ' ';
    }

    return 0;
}

Как работает код?

1. Граф

vector<int> g[N];

g[v] хранит всех соседей вершины v.

если есть ребро 1 -- 2
тогда:
g[1].push_back(2)
g[2].push_back(1)

2. Очередь

queue<int> q;

Очередь нужна, чтобы вершины обрабатывались по порядку. Кто раньше попал в очередь, тот раньше обработается.

q.push(1)
q.push(2)
q.push(3)
q.front() = 1

3. Посещение вершины

used[start] = true;
dist[start] = 0;
q.push(start);

Стартовую вершину сразу отмечаем посещенной. Расстояние до самой себя равно 0.

4. Основной цикл

while (!q.empty()) {
    int v = q.front();
    q.pop();

    for (int to : g[v]) {
        if (!used[to]) {
            used[to] = true;
            dist[to] = dist[v] + 1;
            p[to] = v;
            q.push(to);
        }
    }
}

Пока очередь не пустая, достаем вершину и смотрим ее соседей. Если сосед еще не посещен, добавляем его в очередь.

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

BFS может не только найти расстояние, но и восстановить сам путь. Для этого нужен массив p.

p[to] = v;

Это значит:

мы пришли в вершину to из вершины v

Пример

путь от 1 до 4:
1 → 2 → 4

Тогда:

p[4] = 2
p[2] = 1
p[1] = -1

Чтобы восстановить путь, идем с конца назад по родителям.

vector<int> getPath(int finish) {
    vector<int> path;

    if (!used[finish]) {
        return path;
    }

    for (int v = finish; v != -1; v = p[v]) {
        path.push_back(v);
    }

    reverse(path.begin(), path.end());

    return path;
}

Задача 2: найти кратчайший путь

Дан граф, стартовая вершина s и конечная вершина t. Нужно вывести кратчайший путь от s до t.

Input

Output

1 2 4

Полная реализация с восстановлением пути

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m, s, t;
vector<int> g[N];
bool used[N];
int dist[N];
int p[N];

void bfs(int start) {
    queue<int> q;

    used[start] = true;
    dist[start] = 0;
    p[start] = -1;
    q.push(start);

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int to : g[v]) {
            if (!used[to]) {
                used[to] = true;
                dist[to] = dist[v] + 1;
                p[to] = v;
                q.push(to);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> s >> t;

    for (int i = 1; i <= n; i++) {
        dist[i] = -1;
        p[i] = -1;
    }

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    bfs(s);

    if (!used[t]) {
        cout << -1;
        return 0;
    }

    vector<int> path;

    for (int v = t; v != -1; v = p[v]) {
        path.push_back(v);
    }

    reverse(path.begin(), path.end());

    for (int x : path) {
        cout << x << ' ';
    }

    return 0;
}

BFS на матрице

BFS можно использовать не только в графе, но и в таблице. Например, нужно найти кратчайший путь по клеткам.

Обычно есть поле:

. . . #
. # . .
. . . .

. — можно ходить
# — стена

Из клетки можно ходить в 4 стороны:

вверх, вниз, влево, вправо

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

Задача 3: BFS по клеткам

Дана матрица n × m. Нужно найти минимальное количество шагов от S до F.

Input

3 4
S..#
.#..
...F

Output

Полная реализация BFS на матрице

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int n, m;
char a[N][N];
int dista[N][N];

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    int sx = -1, sy = -1;
    int fx = -1, fy = -1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];

            dista[i][j] = -1;

            if (a[i][j] == 'S') {
                sx = i;
                sy = j;
            }

            if (a[i][j] == 'F') {
                fx = i;
                fy = j;
            }
        }
    }

    queue<pair<int, int>> q;

    dista[sx][sy] = 0;
    q.push({sx, sy});

    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();

        int x = cur.first;
        int y = cur.second;

        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];

            if (nx < 1 || nx > n || ny < 1 || ny > m) {
                continue;
            }

            if (a[nx][ny] == '#') {
                continue;
            }

            if (dista[nx][ny] != -1) {
                continue;
            }

            dista[nx][ny] = dista[x][y] + 1;
            q.push({nx, ny});
        }
    }

    cout << dista[fx][fy];

    return 0;
}

Когда использовать BFS?

Нужно найти кратчайший путь в невзвешенном графе
Нужно найти расстояния от одной вершины до всех
Нужно пройти по клеткам в матрице
Нужно проверить достижимость вершины
Нужно найти количество компонент связности

Если ребра имеют веса, обычный BFS уже не подходит. Тогда часто нужен алгоритм Дейкстры.

Асимптотика

Случай	Время	Память
Граф	O(n + m)	O(n + m)
Матрица n × m	O(n · m)	O(n · m)