Определение

Под обходом понимается последовательное посещение (обработка) вершин графа в определённом порядке. Одним из двух часто использующихся способов обхода является обход в ширину, или BFS (англ. breadth-first search, поиск в ширину). Его иногда также называют волновым, по аналогии с распространяющейся волной.

Суть BFS достаточно проста. Обход начинается с посещения определённой вершины (для обхода всего графа часто выбирается произвольная вершина). Затем алгоритм посещает соседей этой вершины. За ними - соседей соседей, и так далее.

Более формально, пусть \(d[i]\) - расстояние от начальной вершины до вершины с номером \(i\) (длина кратчайшего пути в рёбрах). BFS посещает вершины в порядке возрастания \(d[i]\): от наименее до наиболее отдалённых.

Серым помечены вершины в очереди на посещение, чёрным - уже посещённые.

Алгоритм

Как можно увидеть из иллюстрации, сам алгоритм достаточно тривиален. Поддерживается очередь из вершин для посещения. При посещении очередной вершины в очередь добавляются все её соседи, которые ещё не были посещены и ещё не находятся в очереди. Для проверки, была ли вершина уже посещена, используется массив меток. Изначально \(visited[i] = false\) для всех \(i\) кроме начальной вершины. При добавлении вершины \(i\) в очередь \(visited[i]\) присваивается \(true\).

Реализация

Реализуем простой BFS для графа заданного списком смежности:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
using namespace std;

vector<int> graph[100000];
bool used[100000];      //вместо visited массив меток обычно называют used.

int main() {
    //Ввод графа...

    queue<int> q;
    q.push(0);              //в качестве начальной вершины используем 0.
    used[0] = true;

    while (!q.empty()) {
        int cur = q.front();  //извлекаем из очереди текущую вершину
        q.pop();

        //Здесь должна быть обработка текущей вершины.
        cout << "BFS at vertex " << cur + 1 << endl;

        for (int neighbor: graph[cur]) {    //добавляем всех непосещённых соседей.
            if (!used[neighbor]) {
                q.push(neighbor);
                used[neighbor] = true;
            }
        }
    }
}

Практическое применение: вычисление расстояния до всех вершин

BFS по определению посещает вершины в порядке возрастания расстояния от них до начальной. Поэтому одним из главных его применений является вычисление расстояния от заданной вершины до всех остальных.

Модификация алгоритма, необходимая для этого, минимальна. Пусть при обработке вершины \(i\) мы добавляем в очередь вершину \(j\). Это значит, что кратчайший путь от начальной вершины до вершины \(j\) проходит через вершину \(i\).

Доказательство: допустим, что существует более короткий путь в \(j\), не проходящий через \(i\). Обозначим предпоследнюю вершину этого пути \(k\). Так как путь в \(j\) через \(k\) короче пути в \(j\) через \(i\) можно сделать вывод, что расстояние до \(k\) меньше расстояния до \(i\). Но по определению BFS вершина \(k\) в таком случае была бы уже обработана, а значит, \(j\) бы уже находилась в очереди. Получили противоречие. Следовательно, подходящей вершины \(k\) не существует.

Обозначим расстояние от начальной вершины до вершины \(i\) как \(dst[i]\). В таком случае верно, что \(dst[j] = dst[i] + 1\). Таким образом мы можем рассчитать растояние для всех вершин.

Реализация:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
using namespace std;

vector<int> graph[100000];
bool used[100000];
int dst[100000];

int main() {
    //Ввод графа...

    for (int i = 0; i < 100000; i++) {   //изначально заполним массив dst значением -1
        dst[i] = -1;                     //оно будет обозначать, что расстояние до этой вершины ещё неизвестно
    }

    queue<int> q;
    q.push(0);
    used[0] = true;
    dst[0] = 0;         //теперь при добавлении каждой вершины в очередь мы вычисляем расстояние до неё

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

        for (int neighbor: graph[cur]) {
            if (!used[neighbor]) {
                q.push(neighbor);
                used[neighbor] = true;
                dst[neighbor] = dst[cur] + 1;   //вот и весь код расчёта расстояния
            }
        }
    }

    for (int i = 0; i < n; i++) {
        if (dst[i] != -1) {
            cout << "Distance between vertices 1 and " << i + 1 << " is " << dst[i] << endl;
        } else {
            cout << "Vertex " << i + 1 << " cannot be reached from vertex 1." << endl;
        }
    }
}

Стоит заметить одно важное свойство. Если существуют вершины, в которые невозможно добраться из 1-й вершины, \(dst[i]\) для них будет равно \(-1\). Можно вспомнить об определении связности графа. Если после окончания работы алгоритма в массиве \(dst\) осталось хоть одно значение \(-1\), то граф не является связным. Таким образом BFS можно также использовать для проверки на связность.

BFS с сохранением пути

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

Пусть при обработке вершины \(i\) мы добавляем в очередь вершину \(j\). Это значит, что кратчайший путь от начальной вершины до вершины \(j\) проходит через вершину \(i\) (доказательство выше). Значит последним ребром в кратчайшем пути до \(j\) будет ребро \(i - j\), а весь остальной путь будет совпадать с кратчайшим путём до \(i\). Просто сохраним тот факт, что предыдущей вершиной для \(j\) является \(i\). Для этого будем использовать массив \(prev\). Простой пометки \(prev[j] = i\) хватит для восстановления пути после завершения работы алгоритма.

Реализация:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
using namespace std;

vector<int> graph[100000];
bool used[100000];
int dst[100000];
int pr[100000];   //имя prev уже используется библиотекой, поэтому назовём массив pr

int main() {
    //Ввод графа...

    for (int i = 0; i < 100000; i++) {
        dst[i] = -1;
    }

    queue<int> q;
    q.push(0);
    used[0] = true;
    dst[0] = 0;
    pr[0] = -1;   //Пометка, означающая, что у вершины 0 нет предыдущей.

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

        for (int neighbor: graph[cur]) {
            if (!used[neighbor]) {
                q.push(neighbor);
                used[neighbor] = true;
                dst[neighbor] = dst[cur] + 1;
                pr[neighbor] = cur;   //сохранение предыдущей вершины
            }
        }
    }

    //Восстановим кратчайший путь до вершины k (которую, предполагается, мы уже ввели)
    //Для восстановления пути пройдём его в обратном порядке, начиная с j, и развернём.

    vector<int> path;

    int cur = k;         //текущая вершина пути
    path.push_back(cur);

    while (pr[cur] != -1) {   //пока существует предыдущая вершина
        cur = pr[cur];        //переходим в неё
        path.push_back(cur);    //и дописываем к пути
    }

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

    cout << "Shortest path between vertices 1 and " << k + 1 << " is: " << endl;

    for (int v: path) {
        cout << v + 1 << ", ";
    }
}

Применение BFS без явных графов

Кроме собственно графов, BFS часто используется для поиска путей в прямоугольном поле, состоящем из клеток. В этом поле находится некоторая “фигура” которая может перемещаться согласно определённым условиям. На самом деле, такое поле задаёт граф, вершины которого - клетки поля, а ребро из одной клетки в другую существует, если фигура может совершить соответствующее перемещение.

Такие задачи можно решать без явного построения списка смежности, работая только с самой матрицей. В качестве примера приведём решение следующей задачи:

На шахматной доске размером \(N * N\) (\(1 \le N \le 1000\)) в клетке \((x_1, y_1)\) находится конь. Определить, за сколько ходов он может попасть в клетку \((x_2, y_2)\).

На всякий случай напомним, что конь может ходить “буквой Г” в любом направлении. Математически это значит, что конь может изменить одну из своих координат на \(2\) или \(-2\), а другую на \(1\) или \(-1\). Это даёт нам следующий набор векторов, задающий ходы коня:

\[(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)\]

Решение:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
using namespace std;

int n;
bool used[1000][1000];
int dst[1000][1000];

//Вспомогательная функция для проверки, можем ли мы пойти в заданную клетку.
bool not_visited(int x, int y) {
    return x >= 0 && x < n
        && y >= 0 && y < n
        && !used[x][y];
}

int main() {
    int x1, y1, x2, y2;
    cin >> n >> x1 >> y1 >> x2 >> y2;   //n объявлена глобально

    x1--, y1--, x2--, y2--;     //не забываем про сдвиг координат.

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dst[i][j] = -1;
        }
    }

    queue<pair<int, int>> q;    //Мы храним уже не номера вершин, а координаты клеток.
    q.push({x1, y1});       //Предполагается использование С++11, в противном случае используйте make_pair
    used[x1][y1] = true;
    dst[x1][y1] = 0;

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

        int cx = cur.first, cy = cur.second;

        vector<pair<int, int>> moves {
            {1, 2}, {1, -2}, {-1, 2}, {-1, -2},
            {2, 1}, {2, -1}, {-2, 1}, {-2, -1},
        };

        for (auto move: moves) {
            int dx = move.first, dy = move.second;
            if (not_visited(cx + dx, cy + dy)) {
                q.push({cx + dx, cy + dy});
                used[cx + dx][cy + dy] = true;
                dst[cx + dx][cy + dy] = dst[cx][cy] + 1;
            }
        }
    }

    if (dst[x2][y2] != -1) {
        cout << dst[x2][y2];
    } else {
        cout << "Impossible";
    }
}

Как видите, отличие заключается лишь в том, что вместо перебора соседних вершин из списка смежности, мы вычисляем их на лету, используя возможные ходы фигуры.