从事算法面试辅导这几年我见过太多人在 BFS 上栽跟头。BFS 全称 Breadth First Search中文叫广度优先搜索是算法基础里最常用也最容易被忽视细节的图遍历方式。它的原理一句话就能说清——从一个起点出发先访问所有距离为 1 的邻居再访问所有距离为 2 的邻居像水波一样一层层往外扩散。但真到了写代码的时候队列怎么初始化、visited 数组什么时候标记、怎么判断当前在哪一层、状态怎么压缩各种细节全冒出来了不少人就是卡在这些小地方上。这篇我把 BFS 拆开揉碎讲一遍核心原理、标准代码模板、进阶变体多源 BFS、双向 BFS、0-1 BFS、常见题目的套路拆解最后额外分享一些我实际调试中积累的经验。适合准备算法面试的工程师、打算法竞赛的学生以及所有想一次性把搜索类问题搞明白的朋友。不管你是刚接触算法的初学者还是已经写过不少题但总在一些边界条件上翻车的老手这篇内容应该都能帮上忙。1. 先搞懂 BFS 到底在解决什么问题1.1 从一个生活场景说起想象你在一个陌生的商场里手机没电要找一家特定的奶茶店。最笨的办法是乱逛碰运气但稍微有点策略的人会怎么做从当前位置出发先把同一层的所有店铺都扫一遍没有的话再沿着扶梯上下一层把那一层所有店铺再扫一遍。这种按距离一层层探查的方式就是 BFS 的本质。为什么这么做合理因为 BFS 天然具备按距离递增访问的性质对于无权图每条边代价一样BFS 第一次访问到某个节点时走过的路径一定是最短的。这一点是 BFS 最大的杀手锏——它能在求最短路径的问题里给出最直接、最优的答案不需要像某些暴力枚举方法那样遍历所有路径再挑最优。另一个更贴近日常的例子是朋友的朋友。微信里一个人的好友是第 1 层好友的好友是第 2 层你要找和某个人隔了几层关系的另一个用户用 BFS 从第 0 层自己出发逐层往外扩展找到目标时所在的层数就是答案。这种层级扩散的直觉是所有 BFS 题目的底层原型。1.2 两个关键词队列与分层BFS 的实现核心就两样东西队列和已访问标记。这两样缺一不可。队列先进先出FIFO的特性决定了遍历顺序。你把起点丢进队列然后循环弹出队首的节点把它所有没访问过的邻居塞进队尾。由于队列是先进先出的先进入队列的节点一定先被弹出这保证了浅层的节点先处理深层的节点后处理。换句话说队列本身就是 BFS 分层执行的物理载体。分层是理解 BFS 的另一个关键视角。你可以把 BFS 看成是一棵树的层次遍历第 0 层是起点第 1 层是起点的所有邻居第 2 层是邻居的邻居以此类推。很多 BFS 题目比如求最短步数、求传染时间、求最少转换次数本质上都是在问你目标节点出现在第几层。一旦想通了这一点很多题目套路就是同一个模型换了个故事背景。1.3 什么场景优先选 BFS什么场景别用判断一道题该不该用 BFS我一般看三个信号题目要求最短步数最少次数最快到达这类最优性指标且每一步移动的代价相同问题可以被建模成从初始状态向外扩散的形式扩散一层对应一次操作只需要找到第一个满足条件的解不需要枚举所有解反过来如果题目要求所有可能的路径全部方案数那通常是 DFS 或回溯更合适如果图带权重且要求最短路径那应该上 Dijkstra 算法如果只是判断是否存在一条路径而不关心最短DFS 反而更省内存。搞清楚边界比盲目背模板重要得多。2. 标准代码骨架与核心细节2.1 为什么必须用队列而不是栈很多人刚学 BFS 的时候会问为什么这里用队列换栈行不行答案是不行。如果你用栈遍历顺序就会变成深度优先搜索DFS。这两个算法的核心区别本质上就是数据结构的不同队列的先进先出保证先被发现的节点先被扩展栈的后进先出则会让最新发现的节点先被扩展。举一个直观的例子假设起点 A 有两个邻居 B 和 C。用队列时访问顺序是 A、B、CA 弹出时把 B、C 依次加入队尾弹出顺序就是 B 再 C。用栈时A 弹出后把 C、B 压栈先压 C 再压 B出栈顺序是 B、C。到这里看起来差别不大但随着深度增加两者会走向完全不同的遍历形态队列像水面扩散一层层往外推栈像钻地洞一条路走到黑再退回来。理解了这个区别你就理解了 BFS 和 DFS 的分水岭。2.2 图邻接表版本的标准模板BFS 的模板我建议背到条件反射的程度。以无向图为例节点编号 0 到 n-1邻接表存储from collections import deque def bfs(graph, start): # graph 是邻接表graph[i] 是与节点 i 相邻的节点列表 n len(graph) visited [False] * n dist [-1] * n # 起点到每个节点的最短距离-1 表示不可达 q deque() q.append(start) visited[start] True dist[start] 0 while q: cur q.popleft() for nxt in graph[cur]: if not visited[nxt]: visited[nxt] True dist[nxt] dist[cur] 1 q.append(nxt) return distC 版本也是一样的思路只是容器和语法不同#include queue #include vector std::vectorint bfs(const std::vectorstd::vectorint graph, int start) { int n graph.size(); std::vectorbool visited(n, false); std::vectorint dist(n, -1); std::queueint q; q.push(start); visited[start] true; dist[start] 0; while (!q.empty()) { int cur q.front(); q.pop(); for (int nxt : graph[cur]) { if (!visited[nxt]) { visited[nxt] true; dist[nxt] dist[cur] 1; q.push(nxt); } } } return dist; }这段模板里dist数组不是必须的如果你只关心是否可达把 dist 换成布尔数组即可。但绝大多数面试题最后都要输出多少步多少秒所以直接维护 dist 最省事。注意三个动作要绑定在一起入队前标记 visited、更新 dist、再入队。这个顺序不是随便写的原因在下一节展开。2.3 visited 的标记时机新手最容易错的一行我在辅导过程中见过最多的 BFS bug就是把visited[nxt] True写在弹出节点时而不是入队时。表面看只是一个赋值语句位置不同实际影响非常大。如果在弹出时才标记同一个节点很可能被多个邻居重复入队。举个例子节点 X 有两个邻居 A 和 BA 和 B 又都通向 Y。BFS 处理 A 时如果 Y 还没被标记Y 会被塞进队列接着处理 B发现 Y 依然未访问因为还没轮到弹出 Y于是 Y 又被塞一次。这样一来Y 在队列里出现了两份dist 更新可能出现逻辑混乱队列空间被白白浪费极端情况下甚至会导致死循环或指数级重复扩展。正确做法是入队即标记。原因很简单一旦某个节点被塞进队列它就已经是计划内访问的节点了后续任何路径都不需要再把它加进来。这是保证 BFS 每个节点只入队一次、总时间复杂度为 O(VE) 的关键。这个细节也是很多面试官在代码 review 时会盯住的点。2.4 网格图的 BFS 写法算法题里有一大类是网格迷宫类问题比如岛屿数量、腐烂的橘子、最短路径。网格本质上也是图只是每个节点的邻居是上下左右四个方向某些题是八个方向。这类题不需要显式构造邻接表直接在网格上做 BFS 更简洁高效from collections import deque def grid_bfs(grid, start, target): rows, cols len(grid), len(grid[0]) visited [[False] * cols for _ in range(rows)] dist [[-1] * cols for _ in range(rows)] dirs [(-1, 0), (1, 0), (0, -1), (0, 1)] # 上、下、左、右 q deque() q.append(start) visited[start[0]][start[1]] True dist[start[0]][start[1]] 0 while q: r, c q.popleft() if (r, c) target: return dist[r][c] for dr, dc in dirs: nr, nc r dr, c dc if 0 nr rows and 0 nc cols and not visited[nr][nc] and grid[nr][nc] ! 1: visited[nr][nc] True dist[nr][nc] dist[r][c] 1 q.append((nr, nc)) return -1 # 不可达方向数组dirs是网格 BFS 的灵魂。漏写方向、方向写重复、忘记边界检查都是这类题最常见的低级错误。我自己的习惯是先把边界检查0 nr rows and 0 nc cols这一行固定住再写其他逻辑这样能减少一半以上的低级失误。3. BFS 的进阶变体从入门到熟练3.1 多源 BFS多个起点同时扩散有些问题不是从一个点出发而是从很多点同时出发。最典型的是腐烂的橘子所有腐烂的橘子同时开始感染周围的橘子问多久全部腐烂。如果用单源 BFS你得枚举每个腐烂橘子作为起点各跑一遍然后取最小值逻辑绕、复杂度高而且很容易算错同时感染这个语义。正确思路是多源 BFS把所有腐烂橘子一开始全部放进队列让它们作为一个整体逐层向外扩散。因为所有源点同时推进第一次到达某个新鲜橘子的层数就是它被感染的最早时间。实现上只需要把初始化部分的单一起点入队改成将所有源点入队然后在 BFS 过程中记录层数即可。多源 BFS 的背后有一个非常优雅的建模方式想象一个超级起点它用 0 权边连接到所有真实起点。这个超级起点到任一节点的最短距离就是多源场景下的最早到达时间。理解了这个建模你会发现很多问题比如从多个仓库发货到所有城市的最短时间本质上都是同一道题。3.2 双向 BFS把搜索空间少一半当你明确知道起点和目标点时双向 BFS 是非常实用的优化。它的思路是从起点和终点同时做 BFS各扩一层直到两个搜索前沿相遇。复杂度从单向的 O(b^d) 降到大约 O(2 * b^(d/2))其中 b 是平均分支数d 是最短路径长度。举个直观数字假设每个节点平均有 10 个邻居最短路径长度是 6。单向 BFS 大约要扩展 10^6 量级的节点双向 BFS 每一边只扩 3 层各自扩展约 10^3 量级两边加起来也只有 2000 左右。这个差距是数量级的在处理状态空间大的题目时双向 BFS 往往是把超时改成 AC 的那把钥匙。不过双向 BFS 有条件限制必须知道明确的目标节点不能是找到任意一个满足条件的节点最好每次扩展节点数较少的那一侧减少总扩展量需要两个 visited 集合或一个集合加标记区分两边来判断相遇一种简洁的双向 BFS 写法是用两个哈希集合存储当前层的节点每轮扩散一侧并检查交集def bidirectional_bfs(graph, start, target): if start target: return 0 front, back {start}, {target} visited_front, visited_back {start}, {target} steps 0 while front and back: if len(front) len(back): front, back back, front visited_front, visited_back visited_back, visited_front next_front set() for node in front: for nxt in graph[node]: if nxt in visited_back: return steps 1 if nxt not in visited_front: visited_front.add(nxt) next_front.add(nxt) front next_front steps 1 return -1这里steps的语义比较微妙因为两边交替各走一步返回的步数需要结合场景调整。我个人在实际做题时更偏爱集合逐层扩展的写法而不是双队列写法因为集合天然支持扩展较小的一侧这个优化代码也更好 debug。3.3 0-1 BFS边权只有 0 和 1 的特例如果图的边权只有 0 或 1求最短路有一个比 Dijkstra 更快、比普通 BFS 更通用的做法0-1 BFS。它用双端队列deque边权为 0 的邻居插入队首边权为 1 的邻居插入队尾。这样队列始终保持当前距离更优的节点在前出队顺序天然就是按最短路距离递增的。为什么这个策略有效因为 0 权边不会增加距离应当优先处理1 权边会增加一单位距离放到后面。这个规则保证了每个节点最多入队两次一次通过 0 边到达一次通过 1 边到达整体复杂度 O(VE)比 Dijkstra 的 O((VE)log V) 更快写起来也简单很多。0-1 BFS 最常见的应用场景是带开关状态切换的图。举个典型例子一个迷宫里有传送门站在传送门上可以不花步数传送到另一个位置其他移动各花 1 步。这种题的普通 BFS 会算错因为传送是 0 代价的边而 Dijkstra 又杀鸡用牛刀。0-1 BFS 刚好卡在中间既快又准。3.4 状态压缩 BFS把状态当成节点这是我最想提醒读者的一种 BFS 变体因为它在面试和竞赛里出现频率很高却经常被当作难题处理。核心思想是BFS 的节点不一定非得是坐标或普通编号可以是一个完整的状态。典型例子是华容道类的滑块问题或者某些需要记录哪些位置已经访问过的题目。状态压缩 BFS 的做法是把状态编码成一个可比较的键值通常是整数或字符串然后用哈希表或数组标记这个状态是否访问过。比如一个 15 宫格谜题可以把整张盘面编码成一个整数字符串每移动一次生成新状态BFS 在这个状态图上搜到目标盘面为止。这种题的关键是状态空间的设计。好的状态设计能压缩状态数差的状态设计会让你直接内存爆炸。我记得第一次写这种题时盘面用数组存、visited 用集合存结果状态稍多一点就慢得不行。后来把盘面压成整数、visited 换成长度足够的布尔数组速度和内存都好了很多。遇到这类题先问自己完整描述当前局面最少需要哪些信息这些信息能不能编码成一个整数或短字符串想清楚了再动手。4. 实战套路拆解从模板到题解4.1 迷宫最短路径距离和路径一起求迷宫题是 BFS 的招牌应用。核心套路把每一步移动建模成一条边目标是求从起点到终点的最少步数。这个套路里最难的部分往往不是 BFS 本身而是怎么处理障碍物是否可以重复走是否能往八个方向移动这些条件判断。这里有个常见误区很多人会用 DFS 求最短路然后发现超时。为什么 DFS 不适合因为 DFS 求最短路需要枚举所有可能的路径才能比较出最短而 BFS 第一次到达终点就一定是最短的不需要遍历完整张图。这也是最短路径优先用 BFS路径枚举用 DFS这条黄金法则的来源。如果题目还要求输出完整路径可以在 BFS 扩展时额外维护一个 parent 数组记录当前节点是从哪个节点走过来的搜索完成后从终点一路回溯到起点再反转即可。需要注意的是如果需要按字典序输出路径或者路径有多条BFS 的路径还原会复杂一些。我的建议是先保证基础版做对再在需要时扩展 parent 的逻辑。4.2 按层输出的 BFS树的层序遍历二叉树层序遍历是很多人接触 BFS 的第一道题。它要求把每一层的节点分别放在一个列表里返回二维数组。很多人在这一步就开始迷糊怎么知道某一层在哪里结束标准写法是在每一轮循环开始时先记录当前队列的大小size然后只弹出size个节点。这size个节点就是同一层把它们收集进一个临时列表循环结束后再整体加入结果。这个记录 size 分界的技巧在按层输出、计算最大宽度、逐行处理状态等题目里非常通用。掌握它以后你会发现在树结构以外的网格 BFS 里同样好用——比如求每个感染时间点的感染数量这类带时间戳的问题。4.3 拓扑排序BFS 的另一种面孔拓扑排序用于有向无环图DAG中给节点排序保证所有边从前指向后。其中的 Kahn 算法就是用 BFS 的思想来实现的统计每个节点的入度把所有入度为 0 的节点入队然后不断弹出节点、减少其邻居的入度邻居入度降为 0 时继续入队。最终如果访问的节点数不等于总节点数说明图里有环。很多初学者把拓扑排序当成独立知识点其实它和 BFS 的分层思想完全同源只是分层的依据不是距离而是入度逐步递减的过程。理解了 BFS 的队列驱动逻辑Kahn 算法就是顺理成章的推论。课程安排、编译依赖解析、包管理器解决依赖顺序这类工程场景背后都是同一个算法。4.4 面试前值得刷的 BFS 题目清单如果你时间有限我建议按这个顺序刷覆盖上面提到的所有变体二叉树的层序遍历掌握记录 size 分界岛屿数量掌握网格 BFS 的基本访问控制腐烂的橘子掌握多源 BFS打开转盘锁掌握状态压缩 BFS也是字符串状态建模的好入门单词接龙双向 BFS 的经典题能体会到搜索空间减半的威力迷宫最短路径含传送门版理解 0-1 BFS 的适用场景这几道题刷完BFS 的基本功和变体基本全覆盖。剩下的就是在不同题目里不断强化分层最短状态三个概念的联系。5. 我踩过的坑与调试技巧5.1 常见问题速查表症状原因解法程序死循环、内存暴涨visited 标记缺失或标记时机不对确保入队时立即标记 visited答案比预期大没有用 BFS或层数统计错误检查分层的边界处理按层输出时要记录 size答案比预期小网格边界检查遗漏走到了非法格子补全边界检查0 nr rows 等队列空了但目标没找到目标不可达返回 -1 或题目要求的默认值双向 BFS 步数不准两侧交替扩展的步数语义没统一换成每次扩一层并检查相遇的集合写法dist更新错乱在弹出时才更新 dist 而不是入队时入队同时更新 dist确保首次到达即最短这六个问题我实际在面试辅导和竞赛里都见过真实案例。尤其是第一个死循环加内存暴涨一旦出现基本只能重启容器重跑非常浪费时间。所以我现在写 BFS 代码加入队代码行时会顺手检查三件事visited 标记了吗dist 更新了吗边界检查写全了吗三件事确认完才往下写。5.2 三个独家的调优经验第一个经验能用坐标元组就不建多余的数据结构。网格 BFS 里很多新手喜欢自定义结构体存坐标其实(x, y)元组就够了。这不是性能问题而是代码简洁度直接影响你 Debug 的速度。当然如果追求极限性能比如竞赛里的大数据量可以把二维坐标编码成单个整数idx row * cols col减少元组创建的开销。第二个经验visited 能用一维就用一维。网格题里的 visited 可以用一维布尔数组代替二维下标就是row * cols col。这样空间更紧凑访问速度也略快而且在某些需要位运算标记状态的题目里一维表示几乎是唯一选择。第三个经验写 BFS 之前先在纸上画分层图。遇到复杂的状态转移题先在纸上列出状态是什么、从每个状态能转移到哪些状态、目标状态是什么再标清楚每一层的含义。很多时候你做不出题不是不会 BFS而是状态没建模清楚。BFS 本质上只是一个搬运工状态设计才是真正的难点。这一步多花 5 分钟后面省的可能就是 2 小时。5.3 什么时候 BFS 不是好选择也要学会对 BFS 说不。如果状态空间巨大到千万级以上BFS 的内存开销会非常恐怖这时候要考虑启发式搜索如 A* 算法、DFS 加剪枝、或者寻找数学规律。如果边有权重且不是 0-1 类型求最短路应该用 Dijkstra 或带堆优化的变种普通 BFS 会因为忽略权重而给出错误答案。如果题目只是找一个可行解而不要求最优DFS 往往更省内存因为递归栈的深度通常远小于 BFS 队列可能撑开的宽度。另外BFS 的 visited 空间需要提前规划。无论用数组、哈希表还是位图都要对状态总数有个大致估计。我记忆中一次竞赛写了一个状态数逼近百万的 BFS忘了估算内存结果直接内存超限。后来学会了先算账100 万个状态的布尔数组约 1 MBint 数组约 4 MB如果用位压缩还能再降一个量级。不同的数据结构在极限场景下的差距是致命的提前算清楚能帮你省下大量调试时间。最后再分享一点个人经验我个人的习惯是拿到图遍历或者搜索类题目先问自己三个问题——这是不是从初始状态到目标状态的最短步数问题状态空间有多大内存能不能撑住需要记录完整路径还是只需要最终距离这三个问题答完BFS 是不是合适工具基本就清楚了。BFS 本身不难难的是把它用在恰当的位置上。可能有人觉得 BFS 简单不值得花这么多时间深挖但我在实际写代码中发现越是基础的算法越容易在小细节上翻车少了一个 visited 赋值、多了一次无意义的重复入队、方向数组写错了一个坐标都会导致结果错得莫名其妙。把这些细节吃透之后你再去看 AI 路径规划、网络爬虫的层级抓取、地图导航的层级搜索这些真实场景会发现底层都能看到 BFS 的影子。把模板练熟、把分层这个概念刻进直觉里遇到任何搜索类问题你就已经赢了一半。