BFS | kz-maxx

Түсіндіру

BFS — графты ені бойынша қарау алгоритмі. Толық аты: Breadth-First Search.

BFS графты слой бойынша өтеді.

алдымен старт вершина
кейін расстояние 1 болатын вершина
кейін расстояние 2 болатын вершина
кейін расстояние 3 болатын вершина

BFS ішінде queue, яғни обычная очередь қолданылады.

queue<int> q;

BFS невзвешенный графта shortest path табу үшін жақсы. Невзвешенный граф дегеніміз — барлық реброның бағасы бірдей.

BFS негізгі идеясы

BFS-та біз мыналарды сақтаймыз:

Массив	Не сақтайды
g[v]	v вершинасының көршілерін сақтайды
used[v]	v вершинасына кірдік пе, жоқ па
dist[v]	start-тан v-ға дейінгі расстояние
p[v]	v вершинасының parent-і, path қалпына келтіру үшін

Алгоритм:

1. start вершинасын queue ішіне саламыз
2. queue-дан бір вершина аламыз
3. оның барлық көршілерін қараймыз
4. егер көршіге әлі бармасақ, оны queue ішіне саламыз
5. queue бос болғанша қайталаймыз

Обход мысалы

Мына граф болсын:

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] — parent сақтайды

Задача 1: бір вершинадан расстояние табу

Невзвешенный неориентированный граф берілген. s вершинасынан барлық вершинаға дейінгі расстояние табу керек.

Input

Output

0 1 1 2 2

Бірінші жол:

n = 5 — вершина саны
m = 5 — ребро саны
s = 1 — start вершина

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;

Очередь арқылы вершина ретімен қаралады. Кім queue-ға бұрын кірсе, сол бұрын шығады.

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

3. Start вершина

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

Start вершинасын бірден visited қыламыз. Өзіне дейінгі расстояние 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);
        }
    }
}

Queue бос емес кезде вершина аламыз. Оның барлық көршілерін қараймыз. Егер көршіге әлі бармасақ, queue ішіне саламыз.

Path қалпына келтіру

BFS тек расстояние ғана емес, shortest path-тың өзін де таба алады. Ол үшін p массиві керек.

p[to] = v;

Бұл дегеніміз:

біз to вершинасына v вершинасынан келдік

Мысал

1-ден 4-ке path:
1 → 2 → 4

Онда:

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

Path табу үшін соңынан басына қарай parent арқылы жүреміз.

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: shortest path табу

Граф, start вершина s және finish вершина t берілген. s-тен t-ға дейінгі shortest path шығару керек.

Input

Output

1 2 4

Path-пен толық реализация

#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 тек графта емес, таблицада да қолданылады. Мысалы, клеткалар бойынша shortest path табу керек.

Field осылай болуы мүмкін:

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

. — жүруге болады
# — қабырға, жүруге болмайды

Бір клеткадан 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 қашан қолданылады?

Невзвешенный графта shortest path табу керек болса
Бір вершинадан барлық вершинаға distance керек болса
Матрицадағы клеткалар бойынша жүру керек болса
Бір вершинаға жетуге бола ма, соны тексеру керек болса
Компонента связности санын табу керек болса

Егер реброларда вес болса, обычный BFS жарамайды. Ондайда көбіне Дейкстра алгоритмі керек.

Асимптотика

Жағдай	Уақыт	Память
Граф	O(n + m)	O(n + m)
Матрица n × m	O(n · m)	O(n · m)