广度优先搜索

id: bfs

一、 BFS 是什么

BFS（Breadth-First Search，广度优先搜索）从起点出发，先把距离为 1 的点全部走完，再走距离为 2 的，再走距离为 3 的……像水波一样一圈一圈往外扩。

和 DFS 放在一起看，区别就很清楚了：

DFS 深度优先 BFS 广度优先
走法 一条路走到底，走不通再回退 按距离一层一层扩
用什么装待走的点 递归 / 栈 队列
第一次到达某个点 不一定是最短路 在边权相同的图里一定是最短路
擅长的题 枚举所有方案、连通性、回溯 最短路、最少步数、分层

前置知识：[ Rbook: ]。

二、 为什么 BFS 第一次到达就是最短路

BFS 最短路dsa3

在权值相同的图中寻找最短路径。

  • 无向图
  • 距离

队列有一个关键性质：出队的距离单调不减。

  • 起点的距离是 0，先入队；
  • 每次取出队头 uu，把所有没访问过的邻居 vv 的距离设为 dist(u)+1dist(u)+1 后入队；
  • 队列先进先出，所以所有距离为 dd 的点一定在距离为 d+1d+1 的点之前出队。

于是任何一个点第一次被访问时，拿到的一定是最小距离。如果存在一条更短的路径，那条路径上的点会更早被扩展到，矛盾。

这句话是 BFS 能做无权最短路的全部理由，比背代码重要得多。

三、 图上的 BFS 骨架

queue<int> q;
dist[s] = 0;
q.push(s);                              // 起点入队时就把距离定好
while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v : g[u]) {
        if (dist[v] != -1) continue;    // 已经入过队，跳过
        dist[v] = dist[u] + 1;
        q.push(v);
    }
}

标记必须发生在入队时，不能放在出队时。 如果等出队才标记，同一个点会被它的多个邻居反复入队，队列规模可能指数级膨胀。这是 BFS 最常见的错误。

四、 网格 BFS

网格题把每个格子 (x,y)(x,y) 看成一个点，相邻格子之间连边。用方向数组可以省掉四段重复代码：

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

bool inside(int x, int y) {
    return 1 <= x && x <= n && 1 <= y && y <= m;
}

void bfs_grid(int sx, int sy) {
    memset(dist, -1, sizeof(dist));
    queue<pair<int, int>> q;
    dist[sx][sy] = 0;
    q.push({sx, sy});
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (!inside(nx, ny)) continue;       // 出界
            if (a[nx][ny] == '#') continue;      // 障碍
            if (dist[nx][ny] != -1) continue;    // 已经入过队
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
        }
    }
}

迷宫 BFS 的完整过程：

迷宫 BFSanima1

五、 多源 BFS

有些题有多个起点，问「每个点离最近的起点有多远」。不要对每个起点各跑一次 BFS，而是把所有起点按距离 0 一起入队，然后正常跑：

for (int i = 1; i <= k; i++) {
    dist[sx[i]][sy[i]] = 0;
    q.push({sx[i], sy[i]});
}
// 之后和普通 BFS 完全一样

正确性还是来自「队列按距离单调」：所有源点都在第 0 层，所以第一次到达某个点时，扩展它的那个源点一定是最近的。

六、 两类常见变体

状态 BFS。 当「一个点」不是位置，而是一个局面（若干个数的排列、开关的状态、倒水壶里的水量）时，把局面编码成整数或字符串当作节点。这时判重不能用定长数组，要用 set、map 或哈希表。

0-1 BFS。 边权只有 0 和 1 时，用双端队列：边权为 0 的邻居塞到队头，边权为 1 的塞到队尾。这样队列里仍然保持距离单调，复杂度是 O(n+m)O(n+m)。边权超过 1 就该换 Dijkstra 了。

七、 完整模板

// BFS 求无权图最短路：dist[i] = 从起点 s 到 i 的最少边数，-1 表示不可达
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;

int n, m;
vector<int> g[maxn];
int dist[maxn];

void bfs(int s) {
    // 每跑一次 BFS 都要重置距离
    memset(dist, -1, sizeof(dist));

    queue<int> q;
    dist[s] = 0;
    q.push(s);                             // 入队的同时就确定距离

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

        for (int v : g[u]) {
            if (dist[v] != -1) continue;   // 已经入过队，不再是第一次到达
            dist[v] = dist[u] + 1;         // BFS 保证这是最短距离
            q.push(v);
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);                 // 有向图删掉这一行
    }

    bfs(1);

    for (int i = 1; i <= n; i++) printf("%d\n", dist[i]);
    return 0;
}

八、 易错点

  1. 出队才打标记。重复入队，MLE / TLE。永远在入队时标记。
  2. 忘记判边界。网格题数组越界，结果时对时错，很难查。
  3. 多源 BFS 只把第一个源入队。退化成单源，答案偏大。
  4. dist 用 bool 存。只能判可达，拿不到步数；要用 int，用 -1 表示未访问。
  5. 图不连通时只看 dist[1]。其余点仍是 -1，要逐点判断，或者先分组。
  6. 起点就是终点。循环一次都不进，初始化时要单独处理。

9 相关题解

题目 OJ 难度
填涂颜色 luogu 普及-
马的遍历 luogu 普及-
[USACO10OCT] Lake Counting S luogu 普及-
离开中山路 luogu 普及-
01迷宫 luogu 普及
封锁阳光大学 luogu 普及
Required Length codeforces 普及+/提高-