Tommy Chen home

宽度优先搜索（BFS）

03 Nov 2024

1. 简介

宽度优先搜索（Breadth-First Search，BFS）是一种按距离从近到远遍历状态的方法。它先搜索离起点一步的位置，再搜索离起点两步的位置，然后继续搜索更远的位置。

和 DFS 一条路走到底再回退不同，BFS 会把当前距离相同的状态按顺序处理完，再进入下一层。因此，在每次移动代价都相同的图或网格中，BFS 第一次到达一个位置时，走过的步数就是从起点到该位置的最短步数。

BFS 使用队列保存等待搜索的位置。队头是较早发现的位置，先取出；新发现的位置从队尾加入。队列的先进先出顺序保证了搜索按层进行。

2. 基本思路

以网格为例，BFS 可以按下面的过程进行：

把起点加入队列，并把它的距离设为 0。
取出队头位置，枚举它的上下左右四个相邻格子。
如果相邻格子没有越界、可以通过且未访问过，就把它的距离设为当前距离加 1，并加入队尾。
队列为空时，所有从起点能到达的位置都已搜索完毕。

数组 dist 很适合同时记录距离和访问情况：把所有位置初始化为 -1，-1 表示尚未访问；一旦写入非负距离，就表示该位置已经入队，不需要再次入队。

3. 例子：迷宫中的最短步数

给定一个网格，S 是起点，T 是终点，# 是墙，其他格子可以通过。每次可以向上下左右走一格，要求从 S 走到 T 的最少步数。

因为每一步的代价都是 1，所以可以直接使用 BFS。终点第一次被访问时得到的距离，就是最短步数；如果最后 dist[tx][ty] 仍为 -1，说明终点无法到达。

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

const int N = 110;
int n, m;
char grid[N][N];
int dist[N][N];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int main() {
    cin >> n >> m;

    int sx, sy, tx, ty;
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 'S') sx = i, sy = j;
            if (grid[i][j] == 'T') tx = i, ty = j;
        }
    }

    memset(dist, -1, sizeof dist);
    queue<pair<int, int> > q;
    dist[sx][sy] = 0;
    q.push({sx, sy});

    while (!q.empty()) {
        auto current = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = current.first + dx[i];
            int ny = current.second + dy[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (grid[nx][ny] == '#') continue;
            if (dist[nx][ny] != -1) continue;

            dist[nx][ny] = dist[current.first][current.second] + 1;
            q.push({nx, ny});
        }
    }

    cout << dist[tx][ty];
    return 0;
}

例如，在下面的 3 行 4 列网格中，S 到 T 的最短路线长度为 5：

S...
##.#
...T

每个可以经过的格子最多入队和出队一次，四个方向也只检查一次，因此时间复杂度为 O(nm)，其中 n 和 m 分别是网格的行数和列数。

BFS 的重点是“按层搜索”。当题目要求在每一步代价相同的情况下求最少操作次数、最短步数或最近距离时，可以先思考能否把每个状态看作队列中的一个节点，并用 BFS 从起点一层一层扩展。

宽度优先搜索（BFS）

Related Posts