最近在帮几个准备跳槽的朋友做算法面试复盘发现一个很有意思的现象不管是面大厂还是中厂**BFS广度优先搜索**相关的题目出现频率高得吓人而且越是路径搜索类的题越爱在 BFS 上做文章。更夸张的是很多人 DFS 写得贼溜一到 BFS 就露馅——要么队列用的不对要么不知道什么时候该用 BFS要么写出来的代码又慢又乱。这篇东西我想一次性把 BFS 在路径搜索里的高频考点讲透包括核心原理、模板代码、4 道具有代表性的真题拆解、双向 BFS 优化、面试追问的应对方式以及我刷题和陪跑过程中踩过的坑。内容适合两类人一是刚刷题不久、想系统搞定 BFS 的新手二是已经刷了不少题、但 BFS 题目总是“能做对却说不清”的选手。不管是哪一种这篇都能给你一点实打实的东西。1. 先把底层逻辑吃透BFS 为什么能啃下路径搜索这块硬骨头1.1 队列的层序推进恰好对应最短路径的天然语义很多人背 BFS 模板背得滚瓜烂熟但从没想过一个问题为什么 BFS 第一次搜索到目标点时走过的步数一定是最短路径这要从 BFS 的遍历顺序说起。BFS 的核心数据结构是队列先进先出。它把搜索过程分成一层一层地推进——先访问起点再把起点所有邻居入队然后逐个处理这些邻居每个邻居又把自己的邻居入队……整个过程就像水波一样从中心向外一圈一圈扩散。关键点就在这里第 k 轮处理的节点都是从起点出发走 k 步能到达的节点不多不少。所以当目标点第一次出现在这层节点中时k 就是最短步数因为所有更短步数的可能路径都已经被检查过了。这和 DFS 的“一条路走到黑”完全相反。DFS 找到目标点时的路径长度取决于当前这条递归分支走了多远完全不保证最短。很多新手在“找所有路径”这题没问题一遇到“找最短路径”就懵根源就在这里没有想清楚 BFS 的层序推进天然就是为“最短”服务的。1.2 三种高频 BFS 模板背熟才是真本事BFS 在代码层面积累起来其实就三板斧队列、visited 集合、逐层处理。我用 Python 写最通用的一版模板这个模板可以覆盖 80% 以上的路径搜索题from collections import deque def bfs(start, target): # 1. 初始化队列和已访问集合 queue deque([start]) visited set([start]) step 0 # 2. 队列非空时持续遍历 while queue: # 3. 当前层的节点个数决定本层要处理多少次 size len(queue) for _ in range(size): node queue.popleft() # 4. 判断是否到达目标 if node target: return step # 5. 扩展邻居节点 for neighbor in get_neighbors(node): if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) # 6. 本层处理完步数加一 step 1 # 7. 队列耗尽还没找到目标返回-1 return -1这段代码里的关键是size len(queue)它在每一轮开始时固定住当前层的节点数。如果不这么做把整个队列都 pop 完了再step 1就会把不同层的节点混在一起步数统计直接乱套。这算是新手写 BFS 最容易翻车的地方。还有两个变体也需要熟练掌握。第一个是不需要精确分层的 BFS直接用while queue:循环每次 pop 一个节点处理这种写法适合只关心能否到达、不关心具体步数的场景。第二个是网格题很常见的四方向或八方向扩展写法把邻居生成逻辑从get_neighbors函数改成坐标偏移量数组directions [(1, 0), (-1, 0), (0, 1), (0, -1)] # 上下左右 for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 0: ...后面实战部分会反复用到这些变体建议先把它吃透再往下看。1.3 BFS 和 DFS到底该怎么选这个问题面试必问几乎每个人都被问到过。我的判断标准其实很简单就三条一是问题求最短路径、最少步数、最少操作次数并且每一步的代价相同优先选 BFS。二是问题只求是否存在路径、是否连通、或者要求列出所有可能路径DFS 更合适因为 DFS 实现简单递归回溯天然容易记录路径。三是图非常大、目标点很深但每层的分支很多通常优先考虑双向 BFS 或启发式搜索后面我会单独聊。还有个细节容易被忽略DFS 的空间复杂度通常是 O(h)h 是递归深度BFS 的空间复杂度是 O(w)w 是最大层宽。在二叉树这种层宽通常远大于深度的情况下DFS 更省空间这也是很多二叉树路径题选择 DFS 的原因。但在网格图、单词变换这种搜索空间呈指数膨胀的场景里DFS 的递归深度可能会非常大甚至爆栈BFS 反而更安全。2. 四道高频路径搜索题拆解从模板到实战的完整链路2.1 单词接龙LeetCode 127把字符串变换隐式建模成图题目是这样给你一个开始单词beginWord、一个结束单词endWord还有一个单词表wordList每次只能改变一个字母问从beginWord变到endWord最少需要多少个单词包含首尾。如果不存在变换路径返回 0。很多第一次见到这题的人会愣住这也没有图啊其实这就是 BFS 题型的经典特征——图是隐式的。每个单词是一个节点两个单词如果只有一个字母不同它们之间就有一条边。图的规模可以非常大没必要提前把所有边都建好而是在 BFS 扩展时动态生成邻居。from collections import deque def ladderLength(beginWord, endWord, wordList): wordSet set(wordList) if endWord not in wordSet: return 0 queue deque([beginWord]) visited {beginWord} step 1 # 起点算一个节点 while queue: size len(queue) for _ in range(size): word 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 endWord: return step 1 if new_word in wordSet and new_word not in visited: visited.add(new_word) queue.append(new_word) step 1 return 0这里有两个细节值得注意。第一为什么用wordSet而不用原始数组因为wordSet的查找是 O(1)而数组的in查找是 O(n)。单词长度设为 L字符集大小为 26每层扩展要做 L*26 次字符串拼接和查找操作用数组的话时间复杂度直接多了一个 n 的系数很容易超时。第二改字母时优先检查new_word endWord再判断是否在wordSet里。这算是一个小优化虽然对复杂度没有质的改变但在目标词已经找到时能少一次集合查找。2.2 打开转盘锁LeetCode 752状态空间搜索的教科书案例转盘锁是另一个高频题非常能锻炼“状态”思维。一个四位密码锁每位是 0 到 9每次可以把其中一位向上拨或向下拨一位deadends里的状态不允许到达问从0000拨到target最少需要多少次。这题的关键是把“状态”看成图节点。每个状态比如0000有 8 个邻居4 个位置各往上拨一下、往下拨一下。BFS 在这些状态之间搜索找到目标状态的层数就是最少拨动次数。from collections import deque def openLock(deadends, target): deadSet set(deadends) if 0000 in deadSet: return -1 if target 0000: return 0 queue deque([0000]) visited {0000} step 0 while queue: size len(queue) for _ in range(size): state queue.popleft() if state target: return step # 遍历4个位置 for i in range(4): # 向上拨和向下拨 for d in (1, -1): new_digit (int(state[i]) d) % 10 new_state state[:i] str(new_digit) state[i1:] if new_state not in deadSet and new_state not in visited: visited.add(new_state) queue.append(new_state) step 1 return -1这题至少有三个坑。一个坑是deadends用列表存会导致严重超时必须转成 set。这题的状态空间是 10 的 4 次方一共 10000 个状态看起来不大但如果每次都用列表做in判断最坏情况下每个状态的每次扩展都要遍历整个列表时间复杂度会被放大很多。另一个坑是拨动方向的计算。(int(state[i]) d) % 10这个写法非常关键9往上拨会变成00往下拨会变成9取模运算正好实现这种环形效果。新手很容易写(digit d) % 10时漏掉digit需要先转 int或者忘记取模后要转回 str 才能做字符串拼接。第三个坑是初始化判断。很多人只在循环里判断state target但忽略了起点本身可能就在deadends里、或者起点就是目标值的情况。这两行前置判断看起来不起眼但漏掉任何一个测试用例都会直接报错。2.3 二进制矩阵中的最短路径LeetCode 1091网格题 BFS 的标准姿势网格类 BFS 是面试里出现频率最高的一种因为信息直观、场景贴近真实地图而且变体非常多。拿 1091 这道题来说给你一个 n x n 的二进制网格grid0表示可以通过1表示障碍物只能走八个方向上下左右加四个对角线问从左上角(0, 0)到右下角(n-1, n-1)的最短路径长度。from collections import deque def shortestPathBinaryMatrix(grid): n len(grid) # 起点或终点被障碍物堵住直接返回-1 if grid[0][0] 1 or grid[n-1][n-1] 1: return -1 directions [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)] queue deque([(0, 0)]) visited {(0, 0)} step 1 # 起点算一个单元格 while queue: size len(queue) for _ in range(size): x, y queue.popleft() if x n-1 and y n-1: return step for dx, dy in directions: nx, ny x dx, y dy if (0 nx n and 0 ny n and grid[nx][ny] 0 and (nx, ny) not in visited): visited.add((nx, ny)) queue.append((nx, ny)) step 1 return -1网格题的 BFS 模板基本就是这样但我见过太多人在这题上栽跟头。第一个坑是方向数量弄错。题目说“八个方向”就必须写全 8 个偏移量少写对角线方向会导致部分合法路径找不到。如果题目只说“上下左右”那就只写 4 个方向多写反而可能得出错误答案。看清楚题再动手别默认。第二个坑是访问标记的时机。我见过有人在 pop 节点时再标记 visitednode queue.popleft() if node in visited: continue visited.add(node)这种写法也能工作但队列里可能会塞入大量重复节点导致时间和空间开销大幅上升。正确的做法是在入队时就标记 visited这样一个节点绝不会被加入队列两次搜索空间被严格控制在 O(n^2) 的量级。第三个坑是距离的初始化。起点已经是一个有效路径节点所以步数从 1 开始不是 0。如果题目问的是“需要移动多少步”那可能起点不算步数需要返回step - 1。这种细节一定要结合题目的定义来。2.4 双向 BFS把搜索空间砍半的实战优化上面三道题在面试里属于“基础解法能过”的范畴但面试官经常会追问一句“你这个 BFS 还能优化吗”这时候如果你能说出双向 BFS会是很明显的加分项。双向 BFS 的思路很朴素从起点和目标点同时开始 BFS两边各扩展一层然后在中间相遇。每次扩展时选择节点数更少的那一边扩展这样可以把搜索复杂度从指数级降到大约指数的一半。对于树这种单源结构提升不明显但对图这种多分支结构效果很显著。from collections import deque def bidirectional_bfs(start, target, get_neighbors): if start target: return 0 start_queue deque([start]) target_queue deque([target]) start_visited {start} target_visited {target} step 0 while start_queue and target_queue: step 1 # 总是扩展节点数更少的一侧控制搜索规模 if len(start_queue) len(target_queue): start_queue, target_queue target_queue, start_queue start_visited, target_visited target_visited, start_visited size len(start_queue) for _ in range(size): node start_queue.popleft() for next_node in get_neighbors(node): if next_node in target_visited: return step if next_node not in start_visited: start_visited.add(next_node) start_queue.append(next_node) return -1用双向 BFS 做转盘锁时如果目标状态明确性能提升非常明显。普通 BFS 要扩展接近整个状态空间才能找到目标双向 BFS 通常只需要扩展状态空间的很少一部分。不过它有个限制必须知道明确的目标状态。像单词接龙这种目标词给定的题可以放心用但像“找连通分量”这种没有明确终点的题就没办法用。3. 识别 BFS 题型的三个信号考试时快速判断用什么算法3.1 有“最小/最少/最短”字眼且每步代价相同这是一个非常强的信号。关键词通常是“最少步数”“最短路径”“最少操作次数”“最少点击次数”。要注意的是必须同时满足“每一步的代价相同”这个条件。如果不同的移动有不同的代价那就属于带权最短路径问题BFS 就不适用了得换成 Dijkstra。在实际面试中我通常建议先快速判断如果不是带权图最短路径百分百用 BFS如果是带权图先看权重是否都为正数是正数用 Dijkstra有负数还要考虑 Bellman-Ford。把这条判断链路烂熟于心能避免很多想当然的错误。3.2 分层扩散/传染模型从源头逐步向外蔓延有些题没有明确说求最短路径但问题的本质是分层扩散比如“感染一座岛屿需要多少天”“从所有建筑物出发到某点的最短距离”“腐烂橘子需要几分钟传染完整个网格”。这类题有个共同点初始有多个源点每个源点一层一层向外扩散直到覆盖所有可达区域。对应的技术叫多源 BFS。实现思路很简单初始化时把所有源点一次性放进队列然后正常做分层遍历最后一层遍历完的层数就是答案。拿腐烂橘子那题举例一开始把所有腐烂的橘子坐标放进队列然后一层一层往外扩每一轮让新鲜的橘子腐烂并加入下一层队列直到队列为空或者没有新鲜橘子为止。多源 BFS 的本质是把多个起点看作一个整体从它们共同向外做 BFS复杂度仍是 O(rows * cols)。3.3 状态转移/隐式图把“样子”当节点把“操作”当边这是最容易被忽视的一类也是最容易拉开分数的一类。题目表面上没有图、没有树、没有网格但它定义了一种“状态”以及状态之间的“转移方式”。只要能画出状态图BFS 就自然适用。比如转盘锁的每个四位数字组合是一个状态拨动一位是转移单词接龙里的每个单词是一个状态改变一个字母是转移华容道、拼图游戏、开锁类问题同理。这类题的关键是选择合适的状态表示方式让状态能用可哈希的数据结构表示从而放进 visited 集合。字符串、元组、整数位运算是最常见的三种状态表示方式我建议在解题时优先考虑字符串因为它最直观编码时也不容易出错。3.4 时间复杂度和空间复杂度的套路化分析应对追问BFS 的时间复杂度其实是 O(V E)V 是节点数E 是边数因为 BFS 每个节点入队一次、每条边被访问一次。但不同题型里 V 和 E 的呈现方式不同。网格题的 V 是网格单元数E 是每个格子与邻居构成的边数方向上界为 4 或 8所以复杂度是 O(rows * cols)空间复杂度同样是 O(rows * cols)因为 visited 集合和队列都可能存下所有格子。状态转移题的 V 是状态总数比如转盘锁的状态总数是 10^4单词接龙的状态总数是单词数量乘以可能的变换次数。这类题的复杂度要按状态数来分析不能凭感觉说“就是 O(n)”。回答复杂度追问时我建议先给出 V 和 E 的定义再写出整体复杂度表达式。这样面试官能看出你是真的理解 BFS 的精髓而不是背模板。4. 高频失误与排查技巧我从真实刷题现场总结的避坑清单4.1 visited 标记时机错误导致超时我服务过的一个学员做网格类 BFS 时总爱在 pop 节点之后才标记 visited测试用例少的时候看不出问题一到大规模数据就卡在超时上。我陪他排查时发现同一个节点可能被多个邻居先后加入队列队列里囤了大量重复元素搜索空间被白白放大好几倍。排查方法很简单在节点入队的同时打印一下队列长度如果队列长度随着层数增加膨胀得异常快基本就是这个问题。修复方法也简单把visited.add(node)从 pop 之后移到入队之前。4.2 状态表示选择不合理导致代码又慢又绕有些题目既可以表示成字符串也可以表示成元组还可以压缩成整数。选错表示方式会让代码变得又长又容易出错。比如网格题里的坐标用(x, y)元组就很好可哈希、直观。但如果你用 x * n y 这种整数表示代码就会多一层转换逻辑还容易算错坐标。反过来状态压缩类的题比如某个棋盘状态用字符串会把内存开销拉大很多用整数位运算则更快。核心原则是在满足可哈希的前提下优先选择编码简单、不容易出错的状态表示出现性能瓶颈后再考虑压缩优化。4.3 边界条件判断比算法本身更致命的细节我在 BFS 题上载过最多的跟头不是算法不会写而是边界条件漏判。整理一下我踩过的坑和检查清单起点就是终点时BFS 循环虽然能返回 0但如果你没有提前处理有些模板会返回错误结果起点本身在障碍物里或在 deadends 里时必须提前返回 -1否则队列里的第一个节点就非法网格题里终点被障碍物堵住时也要提前判断。还有一个经常被忽略的是字符串变换时新状态可能不在合法范围内比如数组索引越界这种情况必须加范围判断。4.4 面试现场表现技巧BFS 题最容易被追问的 7 个高概率问题面试官在 BFS 题上很少考“你背会没有”更多是考“你真懂没有”。我整理了被追问概率最高的几个问题提前准备可以大幅提高面试表现。第一问为什么 BFS 能找到最短路径把层序扩散与步数对应的关系讲清楚即可。第二问BFS 的空间复杂度是多少、为什么答队列与 visited 集合的规模上界是最大层宽。第三问怎么避免重复访问答 visited 集合注意说清楚为什么入队时标记比出队时标记更好。第四问什么情况下不能用 BFS答带权最短路径、图极大且层宽呈指数爆炸时需考虑更优算法。第五问双向 BFS 的原理是什么答两棵搜索树从两端同时扩张相交时即为最短因为每层扩展范围远小于单向 BFS。第六问多源 BFS 和普通 BFS 的区别答初始状态从单个变为多个逻辑完全一样。第七问BFS 和 DFS 在递归实现上的区别答 BFS 用队列迭代DFS 可以用递归或栈两者的空间复杂度截然不同。把这些问题想清楚面试中基本能对答如流。5. 刷题路线规划从小白到 BFS 高手的四个阶段5.1 阶段一二叉树层序遍历打底熟悉队列操作二叉树是 BFS 最友好的入门场景因为节点关系透明、层结构天然清晰。建议先刷 102 题二叉树的层序遍历把size len(queue)这个分层技巧吃透然后刷 107 题自底向上的层序遍历、199 题二叉树的右视图、116 题填充每个节点的下一个右侧节点指针。这些题练完之后BFS 的节奏感就建立起来了。5.2 阶段二网格题突击掌握方向数组和边界处理网格题是面试最常考的方向建议按经典题顺序刷200 题岛屿数量、130 题被围绕的区域、542 题 01 矩阵、1091 题二进制矩阵中的最短路径、752 题打开转盘锁。这个阶段的重点不是模板本身而是练习“从题目描述到坐标模型”的转化能力。5.3 阶段三隐式图与状态搜索突破思维瓶颈隐式图题是 BFS 的分水岭能过关的人基本能应对大部分面试题。重点刷 127 题单词接龙、433 题最小基因变化、773 题滑动谜题、909 题蛇梯棋。这个阶段的训练目标是把“状态”作为思考的基本单位不被题目的表象迷惑。5.4 阶段四多源与双向 BFS实现质变到这个阶段你的 BFS 基础已经很扎实了。建议刷 994 题腐烂的橘子多源 BFS、417 题太平洋大西洋水流问题从边界反向多源 BFS、127 题单词接龙双向 BFS、1197 题进击的骑士双向 BFS 大显身手。把这几题吃透BFS 就算彻底拿下了。整个路线刷下来大概 20 道题左右不用贪多关键是每道题都要想清楚“为什么用 BFS、状态是什么、邻居怎么定义、步数怎么计算”。我个人在陪朋友刷题时最大的体会是BFS 压根不是背出来的而是“想出来”的。每次看到一道题先问自己三个问题状态是什么邻居怎么找终点怎么判断想清楚这三个问题模板自然就会浮现在脑子里。与其刷一百道题却一知半解不如用这套思路把 20 道经典题彻底吃透——到那时候不管面试官怎么换着花样出 BFS 题你都能稳稳接住。