BFS这名字刷题的人没有不认识它的。广度优先搜索Breadth-First Search面试手撕代码的常客ACM入门的第一道坎也是很多人从“会写循环”到“开始懂算法”的转折点。我见过太多人卡在BFS上不是理解不了“一层一层扩散”这个思想而是死在实现细节上——队列怎么用、标记数组放哪、层数怎么记录每一步都有坑。这篇东西不搞虚的从原理到模板再到实战排查把BFS彻底讲透新手看完能直接上手写题老手也可以当个查漏补缺的速查手册。1. 核心思路从波纹扩散到队列逐层扫描1.1 BFS到底在搜什么BFS解决的核心问题是“从起点出发按距离由近到远地遍历所有可达状态”。这个词看着文绉绉其实你见过它的无数个现实版往水里丢一颗石子波纹一圈一圈往外荡流感爆发接触者先被隔离接触者的接触者第二批隔离微信群裂变先是你的好友进群然后好友的好友进群。每一圈都比上一圈远一层这就是BFS的直觉模型。对应到计算机里我们把“状态”抽象成图的节点。节点之间能一步到达的关系就是图中的边。BFS做的事情就是从起点开始先搜所有一步能到的点标记为距离1再搜这些点的邻居中没被访问过的标记为距离2以此类推。因为每层都是完整搜完才进入下一层所以BFS有个不可替代的天然属性——在无权图中BFS第一次访问到某个节点时的路径一定是最短路径。DFS做不到这件事A*算法在很大程度上也是在BFS的骨架上加启发式剪枝才做到的。理解这个“首次访问即最短”很关键。它意味着在做最短路径类题目时你可以不用记录所有路径只需要在搜到目标点的瞬间停止即可因为那一刻你走的步数就是最优值。1.2 队列BFS绕不开的数据结构BFS的实现离不开队列。道理并不复杂BFS要求严格的逐层顺序我得先把当前层的节点全部处理完再去处理下一层。队列先进先出的特性天然满足这个时序要求。具体到操作上标准的BFS骨架长这样把起点塞进队列从队首弹出一个节点遍历它的所有邻居如果邻居未访问过就标记“已访问”并入队重复第2步直到队列为空你可能会问为什么用队列不用栈用栈会怎样你可以自己试一下——用栈实现的其实就是DFS它会从起点一直往深处扎而不是逐层扩散那“最短路径”这个性质就没了。我自己刚学时犯过这种错可别走弯路。1.3 首版模板先把BFS“跑起来”不管你是用Python还是C还是JavaBFS的代码长得都差不多。我给你一个最基础的伪代码级别的模板先把框架立起来from collections import deque def bfs(start, target): queue deque([start]) visited set([start]) distance {start: 0} while queue: node queue.popleft() if node target: return distance[node] for neighbor in get_neighbors(node): if neighbor not in visited: visited.add(neighbor) distance[neighbor] distance[node] 1 queue.append(neighbor) return -1 # 找不到路径这个模板里visited集合的作用是防止走回头路distance字典记录每个节点到起点的最短距离。很多人初学时会疑惑为什么要在入队之前就标记visited而不是在出队时再标记这个问题非常关键它直接关系到你能不能AC后面第四部分我会专门讲。2. 实战拆解三类高频BFS题目一次性讲透2.1 网格最短路径矩阵上图论的经典模型网格题是BFS的最常见场景比如LeetCode 1091二进制矩阵中的最短路径、127题单词接龙本质上是单词之间建图、以及各类迷宫题。网格题的核心是把“坐标状态”映射成“节点”。以矩阵中的最短路径为例状态就是(row, col)这个坐标对。从一个格子可以走到上下左右四个方向——大多数题允许走8个方向再加四个斜角。代码实现时方向数组是标配directions [(-1, 0), (1, 0), (0, -1), (0, 1)] # 八个方向的话再加(-1, -1), (-1, 1), (1, -1), (1, 1)循环里做的无非就是三件事算新坐标、判越界、判是否可走。为什么网格题特别适合用BFS因为网格天然就是无权图每一格之间的移动代价都是1BFS的第一层就是上下左右直接相邻的格子第二层就是距离为2的格子。我带你走一遍完整流程起点是(0, 0)终点是(n-1, m-1)队列初始化为(0, 0)弹出一个格子检查它的四个方向如果新位置在矩阵内且不是障碍物且未被访问过标记并入队每扩展一层步数加1直到终点入队的那一刻返回当前步数如果你要求的是“最少步数”那答案就是第一次搜到终点时的层数。如果你要求的是“最短路径长什么样”那你需要额外维护一个prev字典记录“每个节点是从哪个节点来的”最后从终点回溯即可。注意如果你要输出完整路径别忘了最后把路径反转一下因为你是从终点往回回溯的。2.2 连通块计数从“走迷宫”到“数岛屿”BFS的另一大用途是求连通分量。经典题号是LeetCode 200岛屿数量题目给你一个二维网格1代表陆地0代表水让你数有多少块不相连的陆地。这类题的思路完全可复用最短路径的模板唯一的区别是入口不同不是从一个固定起点出发搜到终点而是遍历整个网格每发现一个没访问过的新陆地就以此为起点做一次BFS把这一整块陆地的所有格子都标记为“已访问”计数加一。def num_islands(grid): if not grid: return 0 rows, cols len(grid), len(grid[0]) visited set() count 0 for r in range(rows): for c in range(cols): if grid[r][c] 1 and (r, c) not in visited: count 1 bfs(grid, r, c, visited) # 把这一整片陆地全部标记访问 return count这种“扫描式入口”在很多题里都有变体。比如求最大岛屿面积那就是在每次BFS时统计一下访问了多少节点取最大值。比如求被包围的区域边界上的O和与边界连通的O保留其余全部改成X做法就是从四条边界的O做BFS标记“安全”区域剩下的就是需要翻面的。连通块类题目的特点是考验你对“搜索起点”的灵活选择。别把思维固化在“一个起点搜一个目标”BFS可以用于全过程分片式的遍历。2.3 状态空间BFS每个状态都是一个节点网格题里的“状态”是坐标但BFS能解决的远不止坐标。有些题它的每一个“状态”是一个更复杂的对象——比如一个字符串、一个数字、一个数组排列。我举一个经典的例子打开转盘锁LeetCode 752。你有四个转轮每个转轮可以从0转到9每次只能拧一个转轮一格问你从0000转到目标数字避开所有deadends最少要拧几次。这道题的本质是把每一个四位数字组合看成图中的一个节点。相邻节点的概念是“只改变一位且变化量为1”的数字串。比如0000的邻居就包括1000、0100、0010、0001、9000、0900、0090、0009。你发现没有这个图的概念已经从“物理空间中的路径”抽象成了“状态之间的转移关系”。这就是BFS最强大的地方——只要你能定义出“状态”和“状态之间的一步转移”BFS就能在这张隐式图上帮你找最短路径。状态类题目的技巧在于状态必须能够被哈希。字符串、元组、整数都没问题但要注意如果状态过于复杂可能需要序列化转移要写得干净。开锁问题里每一位往前转一格和往后转一格就是(digits[i] - 0 1) % 10和(digits[i] - 0 9) % 10的关系起点和终点都要明确。有些题的起点不是固定的需要你自己构造这类题一旦做顺了你对“搜索”这个词的理解会上一个台阶搜索不只是在地图上找路它可以是在所有可能状态组成的大森林里找一条通往解的最短路径。3. 做出聪明的选择BFS、DFS与A*算法的差异3.1 BFS与DFS一个讲广度一个讲深度拿到一道搜索题第一反应不应该是“我要用BFS”而是“这题该用BFS还是DFS”。我做个直白的对比对比维度BFSDFS数据结构队列栈或递归空间复杂度存储整层节点O(n)存储当前路径O(log n)或O(n)是否擅长找最短路径擅长无权图不擅长找到的不一定最优适合场景最短路径、最少步数、层数相关连通性判断、路径枚举、回溯求解实现难度略高需要队列低递归很自然一个非常容易记的选型经验如果题目问的是“最少几步”“最短路径”“最快到达”优先选BFS如果题目问的是“是否能到达”“有多少条路”“列出所有可能”DFS更顺手。空间上有个细节值得提DFS用递归实现时栈空间可能被系统限制特别深的递归容易爆栈。这时候哪怕DFS思路是对的你也得改迭代式实现或者换用BFS。C类比赛中对深搜递归深度做到心中有数很重要。3.2 A*算法与BFS同样是搜索差别在哪A算法和BFS的纠葛值得单独说道说道。A可以理解为BFS的“加了导航的最短路径搜索”——它在每一步扩展节点时不再盲目地按层扫而是优先选择“当前代价 估计代价”最小的节点。这里的“估计代价”叫启发式函数记作h(n)。BFS相当于h(n) 0的特殊情况——它完全不知道目标在哪只能一圈圈“无差别攻击”。A*有了启发式函数相当于有了GPS方向感。对比下两者的优缺点BFS的优势实现简单结果绝对最优不需要额外设计启发式函数劣势是大图里搜索空间膨胀得厉害A*的优势在启发式函数设计良好的情况下搜索节点远少于BFS速度和内存都更优劣势是需要针对具体问题设计可采纳的启发式函数函数设计得不好可能会退回BFS甚至更差什么时候用A*比如地图寻路是经典场景。如果你在写一个游戏里的NPC寻路地图很大而且有明确的目标点A*会是明显更优的选择。但刷题面试的搜索引擎里99%的情况BFS就够用了面试官出题时你不可能花大量时间设计启发式搜索也没必要。3.3 我的选型心得面试刷题中的经验法则把我踩过的坑总结成这几条经验第一看到“最短”“最少”“最快”字样第一时间锁定BFS。不要觉得题目太简单很多困难题只是BFS的状态定义复杂搜索框架本身没变。第二如果需要“全排列”“全部方案”考虑DFS回溯。这类题目的解空间常常是树状展开DFS配合剪枝是最自然高效的。第三图特别大、但有明显的目标节点且图结构有几何信息比如网格时思考A*是否值得。这里的关键是你能不能快速写出一个好的启发式函数——最常用的就是曼哈顿距离或欧氏距离。第四不要过度优化。我见过有人对一道100x100网格迷宫题去手写A*结果启发式函数写得不完备答案反而不对。竞赛和面试中正确性和开发速度远大于常数级优化。4. 实操验证一道题带你走完BFS全流程4.1 从零开始输出二叉树层序遍历的BFS写法与其空谈我们直接拿一道“BFS入门必修题”来走全流程——LeetCode 102二叉树的层序遍历。这道题完美契合热搜里的“BFS算法”关键词而且是所有BFS题目里最简单直观的一道。题目问得很直白给你一棵二叉树请你返回每一层节点的值。BFS的思路再自然不过队列一开始放根节点。弹出根节点时它的两个孩子入队。然后在某一时刻队列里装的全是同一层的节点。问题是怎么知道“当前层在哪结束、下一层从哪开始”标准解法是在每一层开始遍历前先取一下当前队列的长度size然后循环处理这个size个节点。这样你就把“这一层”和队列中“以后要处理的层”切开来了。from collections import deque def level_order(root): if not root: return [] result [] queue deque([root]) while queue: level_size len(queue) current_level [] for _ in range(level_size): node queue.popleft() current_level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) return result你现在看到的这个level_size技巧是所有BFS层数管理题的基础。改造成“记录最小深度”LeetCode 111时你只需要在每层开始时判断一下当前层有没有叶子节点有就直接返回当时的深度。改造成“二叉树的右视图”LeetCode 199就是每层取最后一个节点的值。4.2 层数记录的两个流派做BFS题绕不开一个问题走到某个节点时步数是多少怎么记录业界有两个主流写法我分别说下优缺点。流派一每个节点同时记录距离。就像我1.3节模板写的用distance[node] distance[parent] 1。优点是逻辑清晰不依赖层循环缺点是额外占一份跟节点数等量的内存。流派二层级大小控制法。就是4.1代码里level_size的那种做法每处理完一层步数变量加一。优点是省内存代码干净缺点是你要非常明确“当前处理的层数是第几层”稍不留神会差一个数。我的个人习惯是网格题和简单题用流派二使用level_size法状态复杂、转移条件多的时候用流派一直接用字典存距离。两种写法都熟练掌握之后临场选型就不是纠结而是顺手的事。4.3 到达目标即止损BFS的效率窍门很多BFS新手会犯一个毛病——找到目标节点后不停止继续把整个BFS队列跑完。这在一些小数据里可能看不出问题但在大数据量下会造成不必要的浪费。BFS有一个黄金法则在无权图里第一次在队列中弹出或入队目标节点时它对应的路径已经是最短的了这时候应该立刻返回后面的搜索不可能产生更优解。“弹出时判断”和“入队时判断”有一个细微差别。如果我在“入队前判断目标并且返回”有时能省下一层不必要的扩展性能更好但需要注意逻辑正确性。通常我在网格题里会写成if neighbor target: return distance 1这样目标节点根本不需要真正入队我直接在当前层数上加一返回省掉了再弹出目标节点的那次循环。4.4 一道题校验你的BFS功底我通常用这道题来判断一个人BFS是否真的入门了LeetCode 127单词接龙。题目给你一个beginWord、一个endWord和一个单词表每次只能改一个字母问从beginWord变到endWord的最短转换序列长度。这道题你如果只是照着模板机械套用会发现一个棘手的问题当前状态是单词hit它的邻居怎么找你不能像网格那样用方向数组算坐标而是要把hit的每个位置换成a到z共26个字母看新单词在不在单词表里在的话就是可转移的邻居。def ladder_length(beginWord, endWord, wordList): word_set set(wordList) if endWord not in word_set: return 0 queue deque([(beginWord, 1)]) visited set([beginWord]) while queue: word, step queue.popleft() if word endWord: return step for i in range(len(word)): for c in abcdefghijklmnopqrstuvwxyz: if c word[i]: continue new_word word[:i] c word[i1:] if new_word in word_set and new_word not in visited: visited.add(new_word) queue.append((new_word, step 1)) return 0这道题能推导出很多变种。最短单词路径、基因突变题LeetCode 433、甚至八数码问题本质都是“状态生成 BFS”的组合。你把这道题吃透BFS就算真正入门了。5. 进阶思考BFS的边界与细节优化5.1 双向BFS搜索空间直接开根号当搜索空间的规模特别大的时候单向BFS可能面临巨大的队列膨胀。一个非常实用的优化是双向BFS同时从起点和终点向中间搜索两边各扩展一层看两个前沿是否相遇。为什么双向BFS有效单向BFS向外扩展d步需要搜b^d个节点b是平均分支因子双向BFS两边各扩展d/2步总量是2 * b^(d/2)。在b较大时这个优化非常可观。实现上双向BFS不再是“一个队列”而是两个集合或两个队列交替向外扩展。每次优先扩展节点数量少的一边以平衡两边的搜索规模。以刚才的单词接龙为例双向BFS的写法和单向完全不一样——它的endWord都必须被访问到的标记区分开来一边用begin_visited另一边用end_visited。当某个新状态插入时发现它同时存在于两边集合就说明通路找到了。双向BFS不是银弹它的局限性在于目标状态必须明确且唯一。对于“求全图连通块”这类没有明确终点的题双向BFS就不适用了。5.2 状态去重的正确姿势去重是BFS的重中之重。重复状态不只影响效率更会直接导致超时甚至无限循环。去重的核心原则就一句话一个状态入队之后立刻标记为已访问。不要等到从队列里取出来的时候再去标记。如果把这个顺序弄反可能出现两个节点同时把同一个邻居放入队列造成重复入队队列膨胀、重复计算、结果还可能错误。我举个例子节点A和节点B都是当前层的节点它们有一个共同邻居C。如果我们在出队时才把C标记为visited那么A出队时会先扫描到C此时C还没标记C入队然后B出队时再扫描到C此时C依然没标记C再次入队。队列里就有两个C后续处理全部重复。解决方案就是模板里的写法入队前判断是否在visited中不在就加入visited并入队。这个细节我说了多少次因为它真的太容易被忽视了。5.3 坐标访问的常见优化网格类BFS里visited可以用哈希集合存坐标元组也可以用二维布尔数组。哪个更好二维数组访问更快内存占用固定比如visited[r][c] True。哈希集合写起来灵活不用提前知道矩阵大小。绝大多数网格题我推荐用二维布尔数组因为它的访问是O(1)的常数时间不存在哈希碰撞的开销。等你遇到状态不是简单坐标的题目时比如排列、字符串再改用哈希集合不迟。如果坐标范围很大但实际能访问的位置很少用哈希集合更省空间。还有一个小技巧有些题可以直接在原数组上把访问过的格子改成0或#省掉单独的visited数组——但前提是你不介意破坏原数据并且能保证这种修改不会影响其他逻辑。算法竞赛中这种“空间换时间”的做法很常见工程代码里则要小心副作用。5.4 性能损耗的隐藏重灾区字符串拼接处理单词接龙这类字符串BFS时我踩过一个很大的性能坑——字符串拼接。每次生成新单词都用word[:i] c word[i1:]看起来没问题但Python里字符串是不可变对象每次拼接都会创建新字符串循环次数多了性能雪崩。优化思路有两个。一是用列表代替字符串把单词先转成list(word)修改指定索引后再join回来。看着代码长了一点但性能提升很大。二是如果字符集和单词长度都比较小可以预生成所有可能的“下一个状态”避免在BFS循环里反复做字符串操作。我在本地测试过一个10000个单词的用例用列表优化后的BFS比直接用字符串拼接快了将近三倍。这种级别的优化在竞赛题目里往往就是AC和TLE的分界线。6. 避坑指南BFS常见的5个隐蔽错误6.1 错误一visited标记时机不对这个问题我在5.2已经详细讲过了。它在代码上的表现是用pop()之后标记而不是push()的时候标记。症状是队列膨胀、超时、死循环。这是BFS初学者最常见的致命错误之一建议你平时写BFS时形成肌肉记忆入队即标记。6.2 错误二方向数组写错导致越界网格题的directions数组写错一个符号比如(-1, 0)和(1, 0)颠倒会导致搜索方向完全错乱。同时越界判断必须放在“访问邻居”的第一行。我曾见过有人先访问visited[r][c]再判断0 r rows结果一旦r越界直接抛异常。正确顺序必须是先算新坐标 - 先判越界 - 再判其他条件。顺序千万不能反。6.3 错误三起点等于终点的边界条件很多BFS题存在一个隐形的边界起点本身就是终点。这时答案应该是0步但如果你一进入循环就判断“当前节点等于目标”返回的可能是1或者错误值。处理方法是把起点等于终点的判断放在BFS开始之前直接返回。别小看这个条件竞赛题的测试用例往往就爱在这些地方设陷阱。6.4 错误四忽视“不可达”的返回有些题目保证一定有解有些则不保证。你写的BFS如果搜完之后队列空了还没找到目标需要返回一个约定的哨兵值-1、0或[]视题目而定。我见过不少人在LeetCode这类平台上因为忘了处理“无解”情况导致返回值类型错误或者输出错误。模板里最后一行return -1不是摆设真到用的时候能救你一次。6.5 错误五多起点BFS忘记初始化有些题不止一个起点比如多个火源同时蔓延、多个门同时开始搜索。这时你需要把所有起点全部初始化进队列并且所有起点的distance都设为0。如果你只放了一个起点后续的搜索会完全错误。典型题目是LeetCode 54201矩阵和LeetCode 994腐烂的橘子。它们本质上都是“多源BFS”模板和单源BFS几乎没有差别唯一的区别就是初始化队列时把所有源点都放进去。这类题思路通了之后做起来甚至比单源BFS还顺手因为避免了为每个起点单独搜索导致的重复计算。7. 实操心得BFS刷题路线的个人建议BFS要真正吃透光看文章不够动手写题是必须的。我根据自己的学习和带人经验给出一条循序渐进的刷题路线第一阶段做基础模板题。二叉树层序遍历102、填充每个节点的下一个右侧节点指针117、二叉树最小深度111。这些题的核心价值是强化你“队列 层循环”的肌肉记忆。第二阶段上网格题。岛屿数量200、二进制矩阵中的最短路径1091、腐烂的橘子994。这里开始涉及坐标转换、多源BFS、visited优化是BFS从“背模板”到“理解思路”的关键一步。第三阶段挑战状态空间BFS。单词接龙127、打开转盘锁752。如果你能独立做出这两道题可以说BFS这个知识点的理解已经超过大多数同龄的竞争者了。第四阶段优化方向。尝试双向BFS解单词接龙再尝试用A思维分析为什么在某些数据上双向BFS更占优势。这里你可以结合A的启发式思想体会“启发式搜索”和“盲目搜索”的本质差异。BFS是一根线A*和双向BFS都是串在这根线上的珍珠。我个人的体会是BFS最迷人的地方不是它代码多花哨而是它用一种极度朴素的“一圈圈往外扩”的方式为看似复杂的问题提供了清晰的最短路径保障。而且这个思想可以迁移到设计路由算法、分析社交网络传播路径、地图导航等许多实际场景。当你真正理解“队列 visited 逐层扩展”这三板斧后你会发现自己看很多问题的角度都变了任何能定义状态转移的系统都可以用BFS去求解它的最优路径。最后再分享一个小技巧刷BFS题时刻意练习手写队列操作不要总是依赖封装好的数据结构。理解队列底层的“头指针移动”和“环形数组”逻辑对你写C和Java代码时的性能把控会很有帮助。BFS的核心从来不是某种语言的API而是那一层层扩散的逻辑本身。