1. 从一道迷宫题说起BFS凭什么能解最短路如果你刚接触算法竞赛或者刷题圈大概率听过这句话无权图上的最短路用BFS。但很多人只是把这句话背下来真到了做题时——第一步就卡住了为什么要用BFSDFS不行吗什么算“无权图”队列里到底该存什么先说结论在边权全部为1或者看作一步等于一个代价的图里BFS天然具备“按层扩散”的特性先到达某个点的层数一定是最小的。换句话说队列先进先出的机制保证了首次出队访问时一定走的是最短路径。这不是什么高深推论而是队列顺序的自然结果——你从起点出发先处理所有一步能到的点再处理两步能到的点依此类推。这篇文章我会带你完整过一遍BFS求最短路的整个思考链路从模板代码到变式题型从数组初始化到调试技巧把我踩过的坑和排查思路一并写出来。无论你是刚接触图论的萌新还是想系统梳理这类题型的参赛选手相信都会有用。2. 核心思路拆解为什么“先进先出”能保证最短2.1 无权图上的层级扩散模型先明确一个前提BFS求最短路适用范围是无权图或者所有边权相等。如果是带权图比如边权分别为2、5、10那BFS就不适用了得换Dijkstra。为什么因为权重不同时步数少的路径未必代价小。比如从A到C一步直达代价100绕路两步代价3BFS按层扩散会先走到C就结束但实际最短代价是绕路那条。这在有权图里是不成立的。而无权图就好办每条边代价都是1那么路径长度就等于边的数量也等于步数。步数少就是路径短没有例外。BFS的做法是从起点开始先走所有能一步到达的邻居这些邻居的“距离”就是1。然后从这第一批邻居出发找它们的邻居中还没被访问过的点距离标记为2。整个过程像水波扩散一圈圈往外推。这里的关键是拿到某个点时我怎么知道它的距离答案是它的距离 前一个点的距离 1。因为你从某个点走一步到新点步数自然多1。2.2 场景代入地图、迷宫与状态图BFS最短路的经典场景首先是迷宫/地图类问题。一个二维网格0表示空地、1表示障碍物从左上角走到右下角最少需要几步。这种题在各大刷题平台多到成灾但确实是把BFS讲透的最佳案例。其次还有一类容易忽略的场景状态转换图。比如一个密码锁每次可以旋转一位数字问从初始状态到目标状态最少操作多少次又比如一个木板水位问题倒水、倒掉、加水最少几步到指定状态。这种问题里“每个合法的状态”就是一个节点“一次操作”就是一条边而且每次操作的代价相同所以同样能用BFS。还有多源BFS——比如一片区域里有多个火源同时向四周蔓延问某点最早什么时候被烧到或者在一排座位中有多个目标点问所有座位到最近的目标点的距离。这类问题其实也是BFS只是起点不止一个。把这些场景放在一起你会发现共同点非常清晰特征说明节点位置坐标 / 状态表示边一次合法移动 / 一次操作权值均为1一步一代价目标最小步数 / 最短路径长度抓住这个抽象模型很多看起来不像图论的题也能迎刃而解。2.3 为什么DFS不适合求最短路很多初学者会问DFS也能找到终点为什么不用它原因在于DFS走的是“一条路走到黑”第一次找到终点的那条路径未必是最短的。你要得到最短路就得把所有路径都遍历完再比较复杂度指数级爆炸。而且DFS天然配合栈递归适合“是否存在路径”“枚举所有可能方案”这类问题BFS配合队列是按层同步推进适合“最少步数”。这里打个比方DFS像一个在迷宫里闷头走的人走不通就原路退回换一条路再试BFS则像一张渔网从起点均匀铺开所有方向同步向前推进。渔网最先碰到的目标走的距离自然最短——因为渔网各个方向拓展速度是一致的。3. BFS最短路模板与实现细节3.1 完整模板代码Python C先亮出最通用的一版模板拿网格迷宫举例。我用Python写一版再给C一版大家各取所需。from collections import deque def bfs_min_steps(maze, start, end): maze: 二维网格0可走1障碍 start: (x, y) 终点: (x, y) return: 最少步数不可达返回 -1 if not maze or not maze[0]: return -1 rows, cols len(maze), len(maze[0]) # 四个方向 directions [(-1, 0), (1, 0), (0, -1), (0, 1)] # 判空起点和终点合法性 if maze[start[0]][start[1]] 1 or maze[end[0]][end[1]] 1: return -1 visited [[False] * cols for _ in range(rows)] # 其实可以用 dist 数组并初始化为 -1 # visited 和 dist 各有取好见下文 dist [[-1] * cols for _ in range(rows)] q deque() q.append(start) dist[start[0]][start[1]] 0 while q: x, y q.popleft() if (x, y) end: return dist[x][y] for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols: if maze[nx][ny] 0 and dist[nx][ny] -1: dist[nx][ny] dist[x][y] 1 q.append((nx, ny)) return -1C版本#include bits/stdc.h using namespace std; const int dx[4] {-1, 1, 0, 0}; const int dy[4] {0, 0, -1, 1}; int bfs(vectorvectorint maze, pairint,int start, pairint,int end) { int rows maze.size(), cols maze[0].size(); if (maze[start.first][start.second] || maze[end.first][end.second]) return -1; vectorvectorint dist(rows, vectorint(cols, -1)); queuepairint,int q; q.push(start); dist[start.first][start.second] 0; while (!q.empty()) { auto [x, y] q.front(); q.pop(); if (make_pair(x, y) end) return dist[x][y]; for (int i 0; i 4; i) { int nx x dx[i], ny y dy[i]; if (nx 0 nx rows ny 0 ny cols maze[nx][ny] 0 dist[nx][ny] -1) { dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } } return -1; }3.2 每一步的意义从变量到循环拆开讲几个关键点。队列是整个BFS的发动机。每次从队头取出一个点来处理再把新发现且未访问的点加入队尾。因为队列先进先出先被发现的点先被处理这才造就了“按层遍历”的效果。visited / dist 数组用来防止重复访问。没有它BFS会陷入无限循环——因为图里可能有环BFS会反复进入同一个点。用dist数组初始化为-1同时起到了“是否访问过”和“记录步数”两个作用。访问时dist为-1说明还没来过直接更新不为-1说明已经来过跳过。这种写法比单独开一个visited数组更省事。方向数组是网格题目的常用技巧。dx、dy分别表示上下左右四个方向的坐标变化循环一次就等于尝试了四个邻居。要注意在二维数组中“上下”对应行坐标减1或加1“左右”对应列坐标减1或加1别搞混。边界检查是最容易被新手忽略的地方。访问邻居前必须先确认新坐标没有超出网格范围否则会数组越界。我见过不少同学在正规刷题平台上提交时遇到运行时错误检查半天发现是越界。入队时同步更新dist而不是出队时更新。这个细节很关键。如果入队时不更新等出队时才设置距离那么一个点可能被多个邻居同时发现在队列里挤进好多次dist判断就失灵了。正确做法是一旦发现这个点未访问立刻把它标记为“已发现”并设定距离再入队。3.3 记录路径从dist数组反推如果题目不只要求最短步数还要求输出具体路径怎么办很简单在更新dist的同时用一个parent二维数组记录“我是从哪个点过来的”。parent [[None] * cols for _ in range(rows)] # 入队时 parent[nx][ny] (x, y) # 到达终点后从终点沿parent一路回溯到起点代码如下def bfs_with_path(maze, start, end): # ... 类似逻辑额外维护 parent # 到达 end 后 path [] cur end while cur ! start: path.append(cur) cur parent[cur[0]][cur[1]] path.append(start) path.reverse() return path # 从起点到终点的坐标列表注意反推出来的路径是倒序的必须反转一次。另外这种方式只适用于父节点唯一的情况——BFS中每个节点第一次被发现的父节点是唯一的所以路径唯一。不过严格说的话BFS找到的最短路可能有多条这种回溯只记录其中一条。3.4 时间与空间复杂度BFS最短路的时间复杂度在网格图上是O(R×C)在通用图上V个顶点、E条边就是O(VE)。因为每个顶点最多入队一次每条边都会被检查一次。空间复杂度与复杂度同级主要是队列和dist/visited数组的开销也是O(VE)。对绝大多数刷题场景来说这个开销完全可接受。注意如果你用了邻接矩阵来存图复杂度里的E会被V²替代——稀疏图用邻接表更划算稠密图用邻接矩阵反而更快。网格题本身的“邻接关系”是天然的四方向结构不需要显式建图。4. 五种常见变式与题目应对策略4.1 网格迷宫类二维数组BFS这类题目是BFS最基本的应用。二维网格、四方向移动、统计最少步数。模板直接套唯一要留意的是“起点就是终点”这种边界情况直接返回0。还有一个小变种叫“最短路径中的转向次数”——比如地铁换乘最少换几次线。此时“点”还是位置坐标但“边”的含义变了在同一线路上的相邻站移动不算换乘换线路才算。这类问题要么把状态包装成“当前所在线路”要么把换乘看成一种“特殊步骤”加入BFS状态后面会讲到状态BFS的思路。4.2 最少步数类状态BFS与状态压缩有些题目不是“走地图”走的是一张“状态图”。典型例子是“翻硬币”一排硬币每次可以翻转相邻的若干枚问从初始状态翻到目标状态最少需要多少次。这里每个状态就是一个“当前硬币的正反排列”一次性翻转操作就是一条边。BFS直接从初始状态出发一层层生成所有可达状态直到命中目标状态。关键问题在于状态如何表示。如果硬币有N枚状态就有2^N种。N≤20时可以用一个int的二进制位表示硬币的正反1表示正面0表示反面状态转移就是按规则翻转二进制位。这种“用一个整数压住一个状态”的技巧叫状态压缩配合BFS就是“状压BFS”。实际写代码时队列里存int状态visited用一个bool数组下标就是状态值。从一个状态生成邻居时按翻转操作位运算即可。这里我提供一个伪代码框架def bfs_state(start_state, target_state, n): # 状态最大值 2^n - 1 visited [False] * (1 n) q deque([(start_state, 0)]) visited[start_state] True while q: state, step q.popleft() if state target_state: return step for op in operations: # 每种翻转操作 new_state apply(state, op) if not visited[new_state]: visited[new_state] True q.append((new_state, step 1)) return -1这类题的关键除了BFS本身还有状态编码。编码设计得好代码就清晰编码混乱一个状态转移就能把人绕晕。我建议先用小规模数据把状态转移逻辑理清楚再上复杂度优化。4.3 多源BFS多个起点同时扩展多个起点同时向外扩散问某个位置最早被哪个起点覆盖。最经典的应用是“矩阵中每个格子到最近的0的距离”曼哈顿距离把所有值为0的格子作为初始起点全部入队让它们同时开始BFS扩散每个格子第一次被访问时dist就是到最近0的距离这一步的实现很直接初始时把多个起点全部放进队列dist初始为0。BFS开始后所有起点就像比赛起跑一样同时向外扩散谁先“抢”到某个格子谁就赋予它距离。因为所有方向速度相同先到达的起点一定最近。多源BFS的另一个常用场景是“洪水蔓延”多个水源、多个火源同时扩散求某个区域被覆盖的时间。把多个源点同时入队的思路完全不变。很多人问多源BFS和普通BFS不一样吗本质上完全一样只是“起点”不是一个而是一组。可以把多源BFS看成在起点集合之前再加一个虚拟超级源点超级源点到所有起点有一条权值为0的边。但实现时不需要真的建这个点只需把所有起点初始入队。4.4 无权图上的最短路邻接表 BFS当你面对的不是网格而是抽象图——比如社交关系、课程依赖——时就得先把图存起来再跑BFS。# 邻接表建图 from collections import defaultdict, deque def shortest_path_undirected(n, edges, start, target): graph defaultdict(list) for u, v in edges: graph[u].append(v) graph[v].append(u) dist [-1] * n dist[start] 0 q deque([start]) while q: cur q.popleft() if cur target: return dist[cur] for nxt in graph[cur]: if dist[nxt] -1: dist[nxt] dist[cur] 1 q.append(nxt) return -1这里的关键是建图时别漏掉双向边——无向图要加两次。有向图则只加一次。4.5 0-1 BFS扩展带着权值的BFS变种一个很有意思的扩展是“0-1 BFS”图的边权只有0和1两种。此时不能直接用普通BFS但也不用上Dijkstra。技巧是遇到权值为0的边把节点插入队首遇到权值为1的边插入队尾。因为0权边不会增加代价相当于和当前节点一样的层数1权边增加一层要放到下一层处理。使用双端队列deque就能在O(VE)内解决这类问题。from collections import deque def bfs_01(graph, start, n): dist [float(inf)] * n dist[start] 0 dq deque([start]) while dq: u dq.popleft() for v, w in graph[u]: nd dist[u] w if nd dist[v]: dist[v] nd if w 0: dq.appendleft(v) else: dq.append(v) return dist这个变种面试和竞赛都会碰到务必备着。它比Dijkstra更容易实现又比普通BFS适用范围更广。5. 一遍遍试错我踩过的那些坑5.1 队列忘记导出队头写Python时经常忘了q.popleft()的返回值或者写成了q.pop()。必须注意队列取元素是从队头取列表用pop()默认从队尾取会变成“栈”——DFS行为完全不对。C里倒是std::queue的frontpop组合比较明确不太会弄错。5.2 visited标记时机不当有两种常见错误出队时再标visited同一个点可能被多个邻居同时发现导致重复入队队列膨胀距离判断出错。更糟糕的是可能A邻居先入队了但B邻居后入队时发现dist还没被更新又把该点入队一次。处理顺序一乱最短路径就可能被覆盖掉。排查方法在入队时更新dist并标记绝不拖延。入队时标visited这是对的。我知道有些教材用出队标记的写法但在很多题目里那种写法会导致一个点被多次入队严重时直接TLE超时。所以统一用“入队即标记”。5.3 dir方向的顺序搞混上下左右对应的坐标增量很多人记不清。二维数组maze[x][y]中x是行下标y是列下标。所以上(-1, 0)下(1, 0)左(0, -1)右(0, 1)如果把y当成行就会得到“左右”变“上下”的诡异行为。调试时优先检查方向数组。5.4 边界条件漏判起点就是终点、起点是障碍物、终点是障碍物、地图只有一行一列、地图为空——这些边界条件看起来没必要但恰恰是隐藏评测点。凡事先把边界条件写完再跑主逻辑能省掉大量返工。5.5 路径长度从0开始还是从1开始很多人在“初始距离”上犯浑。坐标起点到自身的距离是0这一步很明确。但有的题目把“从起点出发算一步”比如走迷宫问“至少移动几次”起点位置移动已经算一次。遇到这种题要能在模板的基础上微调把起点的dist初始化为1或者返回时加1。建议做题前先花10秒理清题意别急着写代码。5.6 大数据输入时用sys.stdin加速在刷题平台上如果图特别大、输入行特别多Python默认的input()很容易TLE。建议开头直接import sys input sys.stdin.readline这一行往往能把TLE变成AC。C选手则直接用ios::sync_with_stdio(false); cin.tie(0);加速输入输出。6. 调试BFS一套实操排查流程BFS写错了最常见的就是“答案不对”和“超时”两个极端。我的调试顺序一般是这样第一步用小样例肉眼跑一遍。用一个3×3或4×4的地图打印整个dist数组。只要dist数组肉眼看起来是对称、逐层递增的基本问题不大。打印方式for row in dist: print(row)第二步检查队列长度。如果队列长度快速增长、没有收敛趋势多半是visited标记时机不对导致大量重复入队。这时候回看“入队时标记”一条——八成是它。第三步验证方向。单独跑一个从起点到某个近邻点的BFS看看路径是否符合预期。方向错了近邻点就找不到。第四步测边界用例。把起点设成终点、地图全空、地图全是障碍物、起点在角落这类用例单独测能暴露出大部分索引和初始化问题。第五步对比暴力解法。对非常小的数据写一个DFS穷举或直接BFS打印所有路径长度和你的BFS答案对比。如果两者一致说明逻辑没问题不一致在全排列一样的逻辑里找差异。第六步检查变量类型。Python还好C选手要留意int溢出问题——网格很大的时候dist值可能超int范围。不过常规题目int没问题但数据规模大的题建议直接用long long一劳永逸。7. BFS与其他最短路算法的对视把BFS放进整个最短路算法家族里看站在全局角度能帮你更快判断该用什么算法。算法适用图时间复杂度实现难度BFS无权图边权全等O(VE)简单0-1 BFS边权∈{0,1}O(VE)中等Dijkstra非负权图O(E log V)中等Bellman-Ford有负权无负环O(VE)中等偏难Floyd全源最短路O(V³)简单做题时的判断口诀边权全是1直接BFS边权只有0和10-1 BFS边权非负Dijkstra有负数Bellman-Ford或SPFA要求所有点对最短路Floyd或V次Dijkstra。最后再分享一个小技巧我习惯在写BFS之前先画一张“层数示意图”。把起点标为第0层所有一步到达的标第1层两步到达的标第2层画完这张图代码的核心逻辑基本就出来了。算法题卡住的很多时候不是代码能力而是没有把“图是什么”想清楚。BFS就是这么个好东西——一旦想通了一层层的扩散逻辑剩下的一切都是水到渠成。