03 BFS 与最短步数

userId_undefined
吴老师
7月全勤卷王8月全勤卷王10月全勤卷王倔强青铜时间刺客空间掌握者

2026-06-30 18:51:07

发布于：广东

3阅读
0回复
0点赞

03 BFS 与最短步数

一、本阶段目标

学完本阶段，学生要能做到：

1. 理解 BFS 是“一层一层扩展”。
2. 会写图 BFS 和网格 BFS。
3. 理解为什么 BFS 能求无权图最短路。
4. 会处理迷宫最短路、马走日、多源 BFS。
5. 会记录 dist 数组和前驱数组。

二、BFS 的核心思想

BFS，全称 Breadth First Search，广度优先搜索。

通俗理解：

先访问离起点距离为 1 的点
再访问距离为 2 的点
再访问距离为 3 的点
……

所以 BFS 是按“层”扩展的。

这也是它能求无权图最短路的原因：

第一次到达某个点时，一定是经过边数最少的路径。

三、图 BFS 模板

queue<int> q;
memset(dist, -1, sizeof(dist));

dist[s] = 0;
q.push(s);

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

    for (int v : g[u]) {
        if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
}

数组含义：

dist[x] = 起点 s 到 x 的最少边数
如果 dist[x] == -1，表示还没到达过

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

队列里的点按照距离从小到大被处理。

起点距离为 0。

从距离为 0 的点扩展出距离为 1 的点。

从距离为 1 的点扩展出距离为 2 的点。

因此一个点第一次被加入队列时，就是最早能到达它的层数。

如果以后再从更深层到达它，步数只会更大，不可能更短。

五、网格 BFS 模板

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

const int N = 1005;
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};

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

int bfs(int sx, int sy, int tx, int ty) {
    memset(dista, -1, sizeof(dista));
    queue<pair<int, int>> q;

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

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        if (x == tx && y == ty) return dista[x][y];

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

            if (!inside(nx, ny)) continue;
            if (a[nx][ny] == '#') continue;
            if (dista[nx][ny] != -1) continue;

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

    return -1;
}

六、BFS 与 DFS 的区别

问题 DFS BFS
能不能到达 可以 可以
统计连通块 常用 也可以
最少步数 不适合 适合
枚举所有路径 适合 不适合
递归实现 常用 不常用
队列实现 不常用 标准做法

一句话：

问“有没有/有几个”常用 DFS。
问“最少几步”优先 BFS。

七、马走日 BFS

普通网格是四个方向，马走日是八个方向。

int dx[8] = {1, 1, 2, 2, -1, -1, -2, -2};
int dy[8] = {2, -2, 1, -1, 2, -2, 1, -1};

其他写法和普通 BFS 一样。

这类题的本质仍然是：

每个格子是点。
马一步能跳到的格子之间有边。
每条边长度为 1。
所以用 BFS 求最少步数。

八、多源 BFS

多源 BFS 指有多个起点同时出发。

常见题面：

多个感染源同时扩散
多个消防站同时出发
多个怪物同时移动
求每个点离最近源点的距离

做法：

把所有起点的 dist 都设为 0，并全部入队。
然后正常 BFS。

模板：

queue<pair<int, int>> q;
memset(dist, -1, sizeof(dist));

for (auto [x, y] : sources) {
    dist[x][y] = 0;
    q.push({x, y});
}

while (!q.empty()) {
    auto [x, y] = q.front();
    q.pop();

    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (!inside(nx, ny)) continue;
        if (dist[nx][ny] != -1) continue;
        dist[nx][ny] = dist[x][y] + 1;
        q.push({nx, ny});
    }
}

九、记录路径

如果题目要求输出最短路径，可以记录每个点是从哪里来的。

pair<int, int> pre[N][N];

更新时记录：

pre[nx][ny] = {x, y};

还原路径：

vector<pair<int, int>> path;
int x = tx, y = ty;

while (!(x == sx && y == sy)) {
    path.push_back({x, y});
    auto [px, py] = pre[x][y];
    x = px;
    y = py;
}
path.push_back({sx, sy});
reverse(path.begin(), path.end());

十、BFS 常见错误

错误 后果 修正
出队时才标记 同一点可能重复入队很多次 入队时就设置 dist/vis
忘记初始化 dist 为 -1 判断访问状态错误 每组数据初始化
迷宫字符读错 输入无空格时不能用 int 用 char 或 string
把障碍条件写反 走到墙里 明确可走字符
BFS 求带权最短路 答案错误 边权不全为 1 时用 Dijkstra/Floyd
没有检查边界 RE 固定 inside 函数

十一、课堂例题

例题 1：迷宫最短路

题意：从起点到终点，每次上下左右走一步，不能穿墙，求最少步数。

建模：

点：可走格子
边：相邻格子之间的移动
权值：每步都是 1
算法：BFS

例题 2：多源感染

题意：有若干感染点，每秒向四周扩散，问每个位置几秒后被感染。

建模：

点：格子
边：相邻扩散
起点：所有初始感染点
算法：多源 BFS

例题 3：马到每个格子的最短步数

建模：

点：棋盘格子
边：马一步能跳到的位置
算法：BFS

十二、练习题

题号 题名 训练点 建议
P1746 离开中山路 网格 BFS 最短路 必做
P1443 马的遍历 八方向/马走日 BFS 必做
P1135 奇怪的电梯 一维状态 BFS 必做
P1332 血色先锋队 多源 BFS 必做
P1162 填涂颜色 也可用 BFS 做连通块 复习
P1141 01迷宫 连通块 + BFS/DFS 预处理 提高

链接：

https://www.luogu.com.cn/problem/P1746
https://www.luogu.com.cn/problem/P1443
https://www.luogu.com.cn/problem/P1135
https://www.luogu.com.cn/problem/P1332
https://www.luogu.com.cn/problem/P1162
https://www.luogu.com.cn/problem/P1141

十三、本阶段作业

  1. 手写网格 BFS 模板。
  2. 解释 BFS 为什么可以求无权最短路。
  3. 完成 P1746 和 P1443。
  4. 完成 P1332，并说明为什么要把多个源点同时入队。
  5. 拓展：给 P1746 加上路径还原。

十四、本阶段小结

BFS 的关键词：

队列
一层一层
最少步数
无权图最短路
入队时标记

看到“最少几步、最少操作次数、最短经过几条边”，优先考虑 BFS。

userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论