BFSBreadth-First Search广度优先搜索是很多人的第一个图论算法也是最容易被低估的一个。我最早接触BFS是在刷“走迷宫”题目的时候当时觉得这就是一个死板的模板建队列、出队、扩散、入队循环到队列空为止完事。后来做的题目多了才意识到BFS真正厉害的地方不在于这个循环本身而在于“队列里的每一层代表着什么”“什么时候可以提前出答案”“状态怎么设计才不会爆内存”这些看起来隐性问题。这篇就从最底层的原理讲到刷题实战中真正会用到的几种变形把适合BFS处理的场景和需要用DFS或更高级算法的场景一并讲清楚适合刚接触图搜索的初学者也适合想系统梳理BFS脉络的进阶者。1. BFS核心原理——为什么队列能“一层一层”地搜索1.1 树的层序遍历是BFS的最直观雏形理解BFS最简单的方式是回到二叉树层序遍历。想象一棵树上有一个根节点它的左右孩子排在第一层孩子们的子孙排在第二层如果用一个队列先让根节点入队然后每次从队首取出一个节点把它的所有子节点塞到队尾这样做出来的访问顺序一定是根、所有第一层孩子、所有第二层孙辈、所有第三层…… 这在多层结构里就是“按层推进”而不是“一条道走到黑”。BFS在图上的行为完全一致区别只是图上节点可能被多条路径到达需要额外一个visited记录来防止重复访问。很多初学者会把BFS理解成“用队列遍历”这个说法没错但不够本质。BFS的本质是维护了一个边界集合队列里同时存的是当前这一层的待扩展节点。每从队列头部弹出一次就是扩展一个节点每往队列尾部加入一次就是把下一层的候选节点纳入边界。因为队列是先进先出的先入队的节点先被扩展所以同一层的节点一定比下一层的节点先被处理。这个“层的概念”是BFS的关键也是它比DFS更容易在特定问题上得出最优解的根本原因。1.2 无权图最短路为什么“先到达的路径就是最短的”BFS最经典的应用是求无权图所有边权重都为1的最短路径。要明白为什么第一次访问到一个节点走的距离一定是最短的可以用数学归纳法来理解第0层只有起点本身起点到起点的距离为0这是最短的假设第k层的每个节点都被以“最短距离k”首次访问那么从一个第k层节点扩展出来的第k1层邻居从起点到它的路径长度是k1。如果有另一条更短的路径能到达这个邻居长度必然小于k1这意味着在更早的层就该访问到它但一层一层地扩散决定了“更早的层”会在“更晚的层”之前被处理完所以这个更短的路径要么根本不存在要么已经在这个邻居入队时被访问过了。我在实际做题时经常给初学者讲一个生活类比想象你在一个空旷的操场上往水里扔一块石头水波会从落点一圈一圈向外扩散。第一圈是距离1的位置第二圈是距离2的位置每一圈比上一圈半径大1。水波永远不会跳过内圈直接到达外圈。BFS就是这个水波的数字化版本每一轮循环对应一圈扩散这个性质让它在“最少步数”“最短距离”这类问题上天然正确。这也是为什么BFS和动态规划经常出现在同一个题目里的原因很多题目先BFS建图再DP求值两套思想配合起来效率很高。2. BFS的两种主流写法——从模板到手写代码2.1 标准队列模板的四要素写BFS之前先记住四个关键点队列、访问标记、方向/邻居生成、距离数组或步数记录。我把这套模板固定在脑子里之后几乎能应付所有BFS题目。队列可以用Python的deque不要用list因为list的pop(0)是O(n)操作在大数据量下会退化得很厉害。访问标记可以是二维数组、哈希集合或者直接在原数组上打标记。邻居生成最常见的就是上下左右四个方向有些题是八个方向有些题是“改变一个字母得到单词”这种规则总之核心就是“从当前状态能去哪些状态”。模板的骨架大致是下面这个模式我一般习惯在入队时立即标记visited这样可以避免同一个节点被多个邻居重复入队from collections import deque def bfs(start, target, can_pass): # 1. 队列和初始状态 q deque() q.append(start) visited set() visited.add(start) step 0 # 2. 向外扩展 while q: # 3. 处理当前层的所有节点 for _ in range(len(q)): cur q.popleft() if cur target: return step # 4. 生成下一层候选 for nxt in get_neighbors(cur): if nxt not in visited and can_pass(nxt): visited.add(nxt) q.append(nxt) step 1 return -12.2 例题实战模板如何套进“最短路径”题拿LeetCode 1091矩阵中的最短路径来实际走一遍。这个题给一个n乘n的0/1矩阵0表示可以走起点是左上角终点是右下角每一步可以向周围8个方向移动。要计算最短路径长度。用上面的模板start是(0,0)target是(n-1, n-1)can_pass是“坐标未越界且矩阵值为0且未访问”。8个方向可以用两个数组生成或者直接写一个dirs列表dirs [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]步骤计数也很直接初始步数为1起点本身占据一步每扩展一层步数加1。我第一次写这个题时犯过一个典型错误就是在出队时才标记visited结果在本应去重的场景里出现了大量重复入队一个100乘100的矩阵跑出了上千万次循环直接超时。后来改成入队时立刻标记问题就消失了。这算是BFS实现里的一个经典陷阱后面我会专门展开讲。3. BFS和DFS到底怎么选——搜索算法的两条路线3.1 遍历顺序的差异决定了各自的适用场景DFS深度优先搜索走的是“一条路走到黑走不动再回头”的路线递归实现极其简洁两行代码就是一个朴素DFS。BFS走的是“层层推进”的路线牺牲一点代码直观性换来的是天然按距离递增的顺序访问节点。这个差异直接带来了两种算法的分工如果你关心的是“是否存在一条路径”DFS通常更省空间因为递归栈深度等于路径长度而BFS需要维护整个待扩展层的节点最坏情况下空间复杂度是指数级的但如果你关心的是“最短路径多少步”BFS是优先选择因为DFS找到的第一条路径不一定最短要找到最短路径往往需要遍历全部路径做比较复杂度会高很多。实际做题时我会先看题目里的关键词出现“最少步数”“最短路径”“最少操作次数”这类词第一反应就是BFS出现“是否存在”“能不能到达”“所有可能的路径”“回溯枚举”这类词第一反应是DFS或回溯。比如扫雷游戏展开空白格适合DFS因为目标是快速找到一个方向上的连续空白而题目里如果问“从起点到终点的最短路”DFS大概率不是好选项。3.2 空间与时间的取舍一个容易被忽略的维度很多人对比DFS和BFS只看时间不看空间实际上空间复杂度往往才是决定一个搜索算法能不能跑通的关键。DFS用系统递归栈在一条很深的链上可能只需要O(d)的空间其中d是路径深度BFS会在队列里同时保存一层的所有节点如果图的分支因子很大比如每个节点能扩展出100个邻居扩展3层之后队列里就会出现上百万个节点内存直接爆炸。反过来如果图是矮胖型即层数少但每层节点极多DFS就没有明显优势。我在参加算法竞赛时有一个经验法则如果确认是无权图并且要求最短路直接BFS不用犹豫如果题目数据范围极大且只需要连通性判断先用并查集再用DFS最后才考虑BFS如果图是隐式图即状态空间需要动态生成的图比如拼图游戏、魔方状态、字符串变换默认大概率是BFS或双向BFS因为这类题求的往往是“最少步数”。下面这个表是我在选择时常用的快速对照维度BFSDFS实现难度中等需要队列和标记简单递归几行就能写空间复杂度队列最大宽度可能指数级栈最大深度通常O(d)是否保证最短路径无权图下保证不保证需要暴力比较适合场景最短路、最少步数、层相关连通性、回溯、路径枚举、拓扑排序变体典型题目迷宫最短路径、单词接龙、腐烂的橘子岛屿数量、排列组合、数独、图的连通分量3.3 DFS和BFS的混用有些题两条路都要走有一个常被初学者忽略的点BFS和DFS并不是互斥的很多高效解法是两种搜索的配合。经典例子是“在迷宫里找最短路径并打印路径”先用BFS从起点到终点算出距离再用DFS或反向BFS根据距离矩阵回溯出具体路径。前向BFS保证了“距离最短”反向回溯保证了“沿着可行路径走”两套思路合起来才能既拿到最优值又拿到具体方案。还有一种更常见的混用场景是“先用DFS建图再对图做BFS”。比如在括号生成、表达式求值、连通块问题里先用DFS枚举所有可能状态或块结构再把状态之间的关系存入邻接表最后用BFS求某个状态到目标状态的最少变换次数。我在做“滑动谜题”这类题目时就是这么干的状态空间较小但变换规则复杂先用DFS穷举出所有可达状态并建边再用BFS求最少步数代码虽然长一点但每一段的逻辑都变得非常清晰排错也轻松很多。4. BFS到A*从“无脑扩散”到“带指南针的搜索”4.1 A*多出来的启发式函数到底在干什么A算法是BFS的一个升级方向它在BFS的“层序扩散”基础上增加了一个启发式函数h(n)用来估计从当前节点n到目标节点的剩余代价。A每次从优先队列按f(n)g(n)h(n)排序g(n)是从起点到n的已知代价中取出f值最小的节点来扩展而不是像BFS那样严格按层级来。直观上A就像一个有了“指南针”的旅人BFS会向四周均匀撒网A则会优先朝目标方向收缩搜索范围。这里有一个关键点需要分清BFS其实是A在h(n)0时的特例。当所有边的权重都为1且没有启发式信息时A退化成按g值排序的Dijkstra如果所有边的权重都是1Dijkstra又退化成BFS。所以可以这样理解BFS是最基础的地毯式搜索A是有方向性的加速搜索。但A的加速效果完全依赖h(n)的质量如果h(n)设得不好比如高估了实际剩余代价A*甚至会丢掉最优解如果低估太多搜索范围又会变大退化得很接近Dijkstra。4.2 对比什么时候A*能碾压BFS什么时候BFS更稳真实场景里BFS和A的取舍直接和问题规模、启发式信息的质量挂钩。一个特别典型的例子是八数码/十五数码问题BFS要遍历的状态空间极其庞大15数码的完整状态空间大约是15的阶乘量级BFS根本不可能在有限时间内跑完而A配合曼哈顿距离作为启发式能在很短时间内找到最短解。反过来如果问题只是一个平面网格上的简单寻路并且网格尺寸不大BFS代码简洁、无参数依赖、没有任何调优空间反而更稳定A*需要你额外实现优先队列和启发式函数代码量多出一截而且很容易因为h(n)设计不当出现性能浮动。从工程视角看我更愿意用下面几条经验来判断状态空间小于10^6直接用BFS没必要上A*。状态空间大但能设计出“信息丰富”的启发式比如曼哈顿距离、欧氏距离、错位数优先考虑A*。启发式很难设计或者状态之间的转移代价不是统一的考虑Dijkstra而不是A*。游戏地图寻路这种场景A*几乎是标准答案因为地图大但路径方向性明确。值得注意的是A虽然在方向上优于BFS却不一定在时间上优于BFS如果数据集规模太小优先队列的堆操作开销反而会让A更慢。我在实测一些题库数据时棋盘在8×8以下时BFS往往更快但棋盘一变大A的优势立刻显现。所以不要盲目“上A”先估算状态数量和启发式质量再做选择。下面这个表是我在实际选型时常用的快速对照维度BFSA*数据结构普通队列优先队列排序依据入队顺序层级f(n)g(n)h(n)是否一定最短路无权图下保证h(n)可采纳时保证启发式依赖无强烈依赖h(n)质量典型场景状态空间不大的最短路大规模寻路、拼图类问题代码复杂度低中高5. BFS在二维矩阵和状态搜索里的实战拆解5.1 多源BFS腐烂的橘子问题LeetCode 994很多刚入门的人会以为BFS只能从一个起点开始搜索实际上多源BFS在很多题目里是核心考点。LeetCode 994“腐烂的橘子”就是一个经典例子二维数组里0代表空、1代表新鲜橘子、2代表腐烂橘子每分钟腐烂橘子会感染四邻域的新鲜橘子问多少分钟后所有橘子都腐坏。这个题的关键是所有腐烂橘子在时间0时就同时开始感染所以需要把所有腐烂橘子一次性全部入队再统一按层扩散。实现上很简单第一遍遍历时把所有值为2的格子全部加入队列同时统计新鲜橘子数量。然后开始BFS每过一分钟扩展一层每感染一个新橘子就把新鲜橘子数量减1。最后如果新鲜橘子数量为0返回扩展的层数否则返回-1。我特别想提醒的一点是这里你可以不用额外的visited数组直接在原矩阵上把新鲜橘子改成腐烂橘子就行这样既能节省空间又能避免重复访问但要注意不要把本轮已经感染的和下一轮才感染的情况混了因为改完之后它会继续被当作“已腐败”的状态参与判断。多源BFS的思想还可以扩展到“网格中的最近距离”这类题目比如LeetCode 542“01矩阵”求每个0到最近的1的距离。这类题如果对每个0都做一次BFS复杂度是O(n^2)数据一大就会超时正确做法是把所有1入队做一次多源BFS一次跑出所有0到最近1的距离。训练多源BFS有助于建立“反向思维”问题里的多个起始点往往可以合并成一个“虚拟起点”。5.2 状态空间搜索单词接龙LeetCode 127BFS不仅能用在矩阵格子上还能用在“状态”上。LeetCode 127“单词接龙”是BFS在隐式图上最经典的题目之一给定开始单词、结束单词和一个单词字典每次只能改变一个字母问从开始单词到结束单词的最短变换序列长度。这里每个单词是一个节点两个单词之间如果只差一个字母就在图中连边。图本身没有显式给你需要BFS在每次扩展时现场生成邻居。写这类题时有一个性能优化点不要每次枚举字典里的所有单词来判断是否只差一个字母那样复杂度是O(N×L)N是字典大小L是单词长度数据一大就超时。标准做法是穷举当前单词每一位的26种替换然后在字典集合里查询这样每个状态的扩展量是26×L而不是N。我第一次做这题时直接用了双重循环枚举字典在5000个词的用例上跑了接近两秒改成字母替换后瞬间降到几十毫秒。这道题可以看作是BFS在“非网格图”上的标准模板掌握了它很多字符串变换、状态转移类的BFS题都能直接套。另一个可以补充的思路是双向BFS从开始单词和结束单词同时向中间搜索每次扩展节点数较少的那一端当两端的访问集合出现交集时就找到了最短路径。双向BFS在状态空间很大的时候效果非常明显可以把搜索深度变为原来的一半状态数量则是平方根级别的缩减。单词接龙这个题的官方数据范围其实不大很多情况单向BFS也能过但一旦你的起点和终点相距很远双向BFS几乎是必须的优化手段。5.3 拓扑排序视角的BFS课程表LeetCode 207拓扑排序很多人是在学图论时接触的但真正实现的时候会发现它本质上就是一个BFS变体。LeetCode 207“课程表”判断课程之间的先修关系是否存在循环也就是判断有向图是否无环。标准解法是Kahn算法先统计每个节点的入度把所有入度为0的节点放入队列然后反复出队每出队一个节点就把它所有邻居的入度减1减到0就把邻居入队。如果最后出队的节点数量等于总节点数说明图无环否则说明存在环。这个算法没有显式地按“层”推进但它用队列处理节点的顺序完全符合BFS的思想。我遇到不少初学者会把拓扑排序和DFS强绑定认为只有DFS才能做判环实际上Kahn算法配合队列实现起来更直观、更好写。用这个算法还可以顺手求出拓扑序列很多题目会在判环基础上进一步要求输出一种合理的课程安排顺序这时候只需要把出队顺序记录下来就是一组拓扑序。5.4 双向BFS搜索空间爆炸的对策上面单词接龙已经提到了双向BFS这里单独拿出来再拎一下。单向BFS的问题是每扩展一层队列里的节点数可能指数增长很多状态都在“无用”地扩散。双向BFS的思路是让起点和终点各自向外扩散每次扩展节点数更少的一端直到两个方向的搜索前沿相遇。在无向图中双向BFS缩减的搜索空间尤其明显如果目标在第d层单向BFS要访问约b^d个节点双向BFS每边只需访问约b^(d/2)个节点总访问量从指数降为平方根级别。实现双向BFS时有几个容易踩的坑两个方向最好都维护独立的visited集合和距离字典每次扩展完当前层后要检查两个集合是否有交集如果某一方向的队列已经空了说明搜索无法继续可以直接返回无解。我在做“打开转盘锁”LeetCode 752时用双向BFS比单向BFS快了接近5倍从1200ms降到240ms左右。6. BFS中的常见问题与排查技巧实录6.1 边界条件与访问标记的位置写BFS最常见的错误有两个一个是忘了处理边界条件一个是visited标记位置放错。边界条件包括坐标越界、矩阵值不合法、字典里不存在、重复状态等很多人喜欢在生成邻居时才判断边界这没问题但一定要保证判断条件覆盖完整。比如在矩阵里至少要确保行号和列号同时满足0 r m和0 c n少一个条件就可能导致程序越界或者误访问。visited标记位置的问题我在前面已经提过这里再展开一下如果你在出队时才标记visited同一层里的两个不同节点可能同时生成同一个邻居导致这个邻居被重复加入队列两次。虽然最终结果可能依然正确因为重复访问只是浪费但会造成大量额外开销。正确做法是当节点被加入队列的那一刻就标记为已访问这样可以保证队列中永远不会出现重复状态。还有一种特殊情况是如果你在多层循环里修改了原数组作为visited一定不要在回溯时把它改回来否则会重复入队导致死循环。6.2 内存爆炸层数多节点多怎么办BFS空间爆炸是小状态空间题目里不太容易遇到的但一旦出现往往没办法靠简单的参数调整解决。遇到这类问题时我会按优先级尝试以下措施先检查是否真的需要把每个状态都压入队列有些状态可以提前剪枝再考虑用双向BFS来平衡空间消耗如果状态是整数或可以用位运算压缩的尽量用int或位掩码存储状态而不是用字符串如果内存依然吃紧可以尝试用DFS加迭代加深IDDFS用时间换空间。举个简单的例子如果状态是一个3×3的棋盘用字符串存是9个字符但用整数存可能只需要一个int内存差距接近10倍。编译型语言里还可以用数组代替哈希集合做visitedPython里可以用bytearray来代替set以节省大量内存。这些都是实战里很实用的优化手段。6.3 方向数组与邻接表两种图模型下的初始化习惯在矩阵类型的BFS里方向数组的写法直接影响代码的可读性与出错概率。我习惯写成二维列表比如dirs [(0, 1), (0, -1), (1, 0), (-1, 0)]这样在循环里直接for dr, dc in dirs:就能拿到四个方向的偏移量。如果把方向写成一维的重复判断代码会瞬间又臭又长而且少一个方向都不容易一眼看出来。在非矩阵的图模型下邻接表的构建是另一个容易出问题的地方。图论题里BFS之前通常要先建图如果题目给的是稀疏图邻接表可以节省大量空间如果给的是稠密图邻接矩阵反而更快。我在做BFS题时有一个习惯先把问题的图模型确定清楚明确节点是什么、边是什么、是否有向、是否有环然后再写代码。不要一上来直接写循环否则很容易把隐式图的方向搞错。6.4 升级路线01-BFS与其他变形最后补充一个BFS的进阶变体01-BFS适用于边权只有0和1的最短路问题。它的做法是用deque替代普通队列如果移动代价为0就把新节点加入队首如果移动代价为1就加入队尾。这样仍然能保持单调性并且比Dijkstra更快因为不需要优先队列维护堆结构。这个技巧在处理带障碍物的网格寻路、电梯调度问题时非常有用比如LeetCode 1368“使网格图至少有一条有效路径的最小代价”就是一个典型例子。从BFS到双端队列BFS再到A*这个知识链条能覆盖绝大部分搜索题。我个人的体会是不要一开始就追求复杂的算法框架BFS和它的一系列变形已经是极强的基础工具先把队列操作、访问标记、层数统计这三件事吃透再去接触更复杂的变体和优化才不会在写代码时手忙脚乱。最后再分享一个小习惯每写完一个BFS我都习惯性地在脑子里跑一遍数据量最小的用例再跑一遍边界用例比如起点就是终点、图里根本没有路径、矩阵只有一行等这比写完直接提交、被用例卡住了再回头改要高效得多。