刷算法题最怕什么我觉得不是码力不够而是拿到题半天不知道往哪个方向想。BFS广度优先搜索作为路径搜索领域最“朴素”也最常用的一类算法几乎横扫了迷宫寻路、单词转换、状态压缩、棋盘操作等一大波高频题。很多同学刷到BFS就觉得“不就是队列套模板嘛”可真到面试现场遇到一道变形题就发懵其实是因为没有把BFS背后的状态空间思维吃透。这篇文章我就把自己刷BFS高频题的经验完整拆一遍从最核心的队列模板开始讲到双向BFS、网格遍历、隐式图建模、状态压缩再到TLE和内存爆炸的排查技巧最后给出我总结的“四步解题法”。不管你是准备校招还是社招或者单纯想把路径搜索这类题做明白这篇都值得仔细看一遍尤其适合那种“模板背得滚瓜烂熟但新题还是不会”的阶段。1. BFS到底在解决什么问题1.1 从“找最短路径”说起BFS的核心能力是“在无权图中找最短路径”。这句话听起来很抽象但把它放到具体场景里就特别好懂。假设你站在一个迷宫的起点每次可以走一格问走到终点最少需要几步。这个问题天然适合BFS因为它会按照“起点走1步能到的格子、走2步能到的格子、走3步能到的格子”这样一层一层往外扩。我知道很多人第一次接触BFS时看的是树的层序遍历觉得那只是“一层一层打印”。但树其实是图的特例BFS真正厉害的地方在于当所有边的权重都相等比如每走一步代价是1时第一次到达目标节点走的步数一定是最短的。这个结论是BFS所有应用的基石。你可以把BFS想象成往水里扔一颗石子水波一圈一圈往外推先碰到岸边的波纹一定是最短的路径。这个类比我每次讲给新人都很管用因为它把“广度优先”这个抽象概念直接变成了视觉记忆。理解了这件事你再看题目就会有种“原来如此”的感觉二进制矩阵最短路径、打开转盘锁最少转动次数、单词接龙最少转换次数本质上全是“无权图最短路径”的换皮题。1.2 BFS和DFS的本质差异面试的时候几乎必问“BFS和DFS的区别”而且很多人只会答“一个用队列一个用栈”。我这里直接把本质差异摊开讲你理解了以后就再也不会混淆。BFS用队列讲究的是“层层推进”先探索离起点近的区域再探索远的区域。DFS用栈或递归讲究的是“一条路走到黑”走不通再回头。这个策略上的差异直接决定了两者适合解决的问题完全不同BFS在无权图里能找到最短路径DFS在可达性判断、拓扑排序、回溯枚举上更自然。从空间复杂度看BFS在最坏情况下需要存储一整层节点也就是O(分支系数^深度)DFS只需要存当前路径上的节点最坏情况下只需要O(深度)。这两个量谁大谁小不好说要看图形状。比如深度很深但分支很少的图DFS省空间深度很浅但分支爆炸的图BFS反而占优。我在面试中见过不少同学答“BFS空间一定比DFS大”这其实不对一定要具体问题具体分析。对比维度BFSDFS核心数据结构队列栈 / 递归搜索顺序按层扩展沿分支深入最短路径无权图下能找到最优解要遍历全部路径才能确定空间复杂度最坏O(分支^深度)最坏O(深度)典型应用最短步数、层次遍历、多源扩散连通性、回溯、拓扑排序说句实在话面试题里只要出现“最少几步”“最短路径”“最小操作次数”这类关键词第一反应一定是BFS。1.3 状态空间思维所有BFS题都是状态转移这是我想重点强调的一个思维模式也是从“会做模板题”到“能解新题”的关键分水岭。BFS题里节点不一定是网格坐标可以是任何“状态”。比如“打开转盘锁”当前锁的密码四位数就是一个状态“单词接龙”当前单词就是一个状态“八数码问题”棋盘上所有数字的排列就是一个状态。每条BFS的边就是一个合法操作拨动一位数字、替换一个字母、移动一次空格。一旦你接受了“状态作为节点操作作为边”的建模方式再奇怪的题目都能套进BFS框架。我个人的习惯是拿到题先问自己三句话当前状态怎么表示从一个状态能转移到哪些新状态什么条件下停止搜索这三个问题想明白代码只是最后一步。比如“腐烂的橘子”这道题初始状态是所有腐烂橘子的位置集合操作是“每个腐烂橘子让上下左右的新鲜橘子感染”终止条件是所有新鲜橘子都腐烂或者无法继续感染。你会发现这正是多源BFS。所以刷BFS题最该练的不是背模板而是把题面转换成状态图图出来了代码自然就顺了。2. 模板不是万能的但先背熟这几套2.1 经典队列模板先给一套我用了很多年的BFS模板这套模板能覆盖80%的题。我建议你把它敲熟但不是死记硬背而是理解每一行在干什么。from collections import deque def bfs(start, target): q deque() q.append(start) visited set() visited.add(start) step 0 while q: for _ in range(len(q)): cur q.popleft() if cur target: return step for nxt in get_neighbors(cur): if nxt not in visited: visited.add(nxt) q.append(nxt) step 1 return -1这套模板有三个关键细节漏一个都可能出问题。第一个细节是for _ in range(len(q))分层。这个循环保证了统计步数时是“一层一层”加的而不是每个节点单独加一。如果去掉分层循环只在每次pop时加一那返回的就不是最短层数了。第二个细节是visited.add(nxt)要放在入队时立刻执行而不是等节点出队的时候再标记。为什么因为BFS是分层的同一个节点可能同时被多个邻居发现如果等出队再标记队列里会塞进大量重复节点不光慢还可能死循环。我在LeetCode讨论区见过太多次这个错误请务必记牢。第三个细节是get_neighbors(cur)要单独抽成一个函数。我见过很多人把邻居生成的逻辑写在主循环里结果代码越写越长查错特别痛苦。抽成独立函数以后调debug也方便面试时讲思路也更清晰。2.2 分层遍历模板经典模板虽然够用但有一类题会明确要求“按层输出”或者“记录每一层的状态”这时候我更喜欢单独拆一个分层遍历模板。from collections import deque def level_order(start): q deque([start]) visited {start} level 0 while q: print(flevel {level}:, list(q)) size len(q) for _ in range(size): cur q.popleft() for nxt in get_neighbors(cur): if nxt not in visited: visited.add(nxt) q.append(nxt) level 1“腐烂的橘子”这类多源扩散题用分层模板写特别清晰每一轮就是“过了一天”新鲜橘子在这个时间片内被感染。另外二叉树的锯齿形层序遍历也适合这种模板区别只是奇数层反着输出。我建议把分层模板练到条件反射因为很多题目不会直接说“求最少步数”而是说“求感染天数”“求扩散轮数”这时候你要能反应过来它就是在分层。2.3 双向BFS模板高频优化如果你已经把经典BFS刷熟了下一步非常建议学双向BFS。这种优化在单词接龙、打开转盘锁这类题里表现极好因为状态空间大会导致单向BFS队列指数膨胀而双向扩散能让搜索量减掉一个量级。核心思路特别简单从起点和终点同时开始BFS每次扩展节点数较少的那一侧两边相遇就意味着找到了一条路径。因为两边都只扩展了深度的一半所以总节点数大幅下降。from collections import deque def bidirectional_bfs(start, target, get_neighbors): if start target: return 0 q_start deque([start]) q_target deque([target]) visited_start {start: 0} visited_target {target: 0} while q_start and q_target: if len(q_start) len(q_target): res expand(q_start, visited_start, visited_target, get_neighbors) else: res expand(q_target, visited_target, visited_start, get_neighbors) if res is not None: return res return -1 def expand(q, visited_cur, visited_other, get_neighbors): size len(q) for _ in range(size): cur q.popleft() dist visited_cur[cur] for nxt in get_neighbors(cur): if nxt in visited_other: return dist 1 visited_other[nxt] if nxt not in visited_cur: visited_cur[nxt] dist 1 q.append(nxt) return None注意这里我用了visited_start和visited_target两个字典存的是“到某个状态的距离”这是为了方便相遇时计算总步数。每次扩展哪一侧取决于两边队列长度谁小就扩谁。这种“谁小扩谁”的策略不是玄学它能有效控制搜索总量。我自己用下来双向BFS在单词接龙这种数据上通常能比单向快好几倍。不过有个前提条件你要能明确知道target状态如果题目只要求“到达某个满足条件的未知状态”那就没法双向搜索只能老老实实用单向BFS。2.4 什么时候不能用BFS背了模板容易陷入一个误区看到“最短”就无脑上BFS。但有几个场景BFS并不是最优解甚至根本没法用我踩过坑现在就提前给你排掉。第一种边的权重不相同。BFS只能处理每步代价相等的图如果不同路径的移动代价不一样比如走平路消耗1爬山消耗5那第一次到达终点的路径就不一定是最优的这时候应该用Dijkstra算法或者带优先队列的变种。第二种状态空间无穷大。如果每个节点能无限生成新状态队列根本不可能清空。比如“无限棋盘上从A走到B最少多少步”虽然实际有解但直接BFS会爆炸需要用数学或者启发式搜索来限定方向。第三种只要求判断是否存在路径不要求最短。此时DFS往往更省空间因为你不需要保留整层节点递归栈的深度通常远小于BFS队列里的节点数。尤其在大图上DFS可能稳定跑完BFS直接内存爆掉。所以正确地使用姿势是先判断图是否无权再判断是否要最短路径最后才决定用不用BFS。3. 高频题目拆解从迷宫到单词梯3.1 网格类岛屿数量/腐烂的橘子网格类是BFS里最容易上手的题型因为状态就是坐标你不需要额外抽象。先看“岛屿数量”这道题。给你一个二维网格1表示陆地0表示水问有多少个岛屿。这类题本质上是在问“图中有多少个连通块”。BFS的做法是遍历每个格子只要遇到没访问过的陆地就把它所在整个岛屿的所有格子用BFS标记为已访问岛屿数量加一。这里的visited可以直接用二维布尔数组也可以把原数组的1改成0省掉额外空间。我个人更喜欢直接标记原数组但面试时最好先说清楚“我会把已访问的格子改成0避免额外空间”显得你考虑过复杂度。再看“腐烂的橘子”。这道题就是经典的多源BFS初始时所有腐烂橘子都在队列里然后每分钟向外扩散一次。实现时要注意统计新鲜橘子的总数每感染一个就减一最后如果新鲜橘子还有剩余说明无法全部腐烂返回-1。还有一个容易忽略的边界条件是初始就没有新鲜橘子那答案应该是0。我在第一次写这道题时就没处理这个边界直接返回了步数结果少算了一天。网格类题目的另一个共同要点是方向数组。上下左右四个方向我习惯写成dirs [(1, 0), (-1, 0), (0, 1), (0, -1)]这样写能少很多重复代码。如果是八方向题比如二进制矩阵最短路径再补上四个斜角方向。3.2 迷宫寻路矩阵中的最短路径拿LeetCode 1091“二进制矩阵中的最短路径”来举例这道题我面试时遇到过非常有代表性。题目给一个n乘n的01矩阵0表示可走1表示障碍从左上角走到右下角可以走8个方向问最少多少步。这题的坑有两个。第一个是“8个方向”不要漏很多人习惯性只写上下左右。第二个是初始起点是障碍物时直接返回-1以及当n等于1时答案就是1因为不需要移动就已经在终点。写法上就是经典BFS队列初始放入(0, 0)visited标记起点每次扩展8个方向注意越界判断和障碍判断。用一个dist矩阵记录每个格子的最短步数也可以直接在每个节点里带步数。因为起点本身就是一步所以初始step要设为1而不是0。这个问题特别容易错我就曾经在“返回0”和“返回1”之间纠结了半天。你把这题做明白以后类似的迷宫题基本就是换汤不换药。唯一要注意的是有些题会加入更复杂的移动限制比如只能往右或往下或者有传送门那就要在状态里多记一个维度后面我会讲到。3.3 字符串转换单词接龙LeetCode 127“单词接龙”是BFS题里非常有代表性的一道也是很多人第一次接触“隐式图”概念的地方。题目给你一个起始单词、一个结束单词和一个单词列表每次只能改变一个字母问能否从start转换到end最少需要几次转换。这道题难在你要反应过来它是一张图每个单词是节点相差一个字母的两个单词之间有边。最直观的建图方式是对每个单词遍历列表里其他所有单词判断是否只差一个字符。这个做法的时间复杂度是O(n^2 * L)n是单词数量L是单词长度。如果n是几千还勉强能跑如果n上万直接TLE。更好的做法是“按字母模式”生成邻居。比如单词hit可以生成模式*it、h*t、hi*然后建立一个模式到单词列表的映射。BFS扩展时枚举当前单词的所有模式再通过映射找到候选邻居。这样每个单词生成邻居的代价是O(L*26)整体远优于O(n^2)。我在实战里用这个方法单词列表一万个也能轻松过。这里我特别想提醒双向BFS在单词接龙上效果拔群因为单词列表很大单向BFS队列可能迅速膨胀。用我之前给的双向BFS模板从start和end同时搜速度能提升很多。但是要注意如果end本身不在单词列表里题目一般会给出限制实际写的时候最好判断一下。3.4 隐式图打开转盘锁LeetCode 752“打开转盘锁”也是经典题。锁有四个拨盘每个拨盘是0到9每次可以上下拨动一个拨盘。给定一个死亡列表如果转到死亡密码就锁死问从0000到target密码最少需要多少步。很多人第一眼觉得这题根本不像图但用“状态就是四位数密码”来想就通了。节点是0000到9999之间所有密码去掉死亡密码边的含义是“向上拨一格或向下拨一格”。例如0000可以转到1000、9000、0100、0900、0010、0090、0001、0009一共8个邻居。这是典型的隐式图不需要真的去建图只要在BFS里动态生成邻居。实现时有个小技巧对数字0减1会变成-1对9加1会变成10所以要做模10处理比如(d - 1 10) % 10和(d 1) % 10。另外visited集合除了要存已访问状态还要把所有死亡密码预先放进去这样BFS就不会走到死亡状态。我写这题时犯过一个典型错误把密码当成整数处理结果0000和0分不清。后来我改用字符串表示状态操作字符串里的每个字符代码一下子清晰了很多。所以遇到前缀有意义的题目字符串往往比整数更安全。4. 实操过程与核心环节实现4.1 从输入到状态设计讲了这么多题你现在最需要的是一套能直接套用的实操方法。我自己的BFS四步法是这样第一步抽象状态。想清楚“当前走到了哪一步”这就是节点。状态可以是一个坐标、一个字符串、一个元组甚至一个位掩码。好的状态定义应该包含所有必要信息并且能唯一标识当前局面。第二步定义邻居。问自己“当前状态通过一次合法操作能到哪些状态”也就是生成邻居的函数。这个函数是BFS的核心代码写得不清晰后面全乱。第三步设计visited。思考“什么算已经访问过”用set、二维数组还是位数组。记住一个原则能放visited的都在入队时放。第四步确定答案。想清楚什么时候返回步数是节点等于目标还是达到某一层还是队列为空就返回-1。这个方法我用在无数道题上每次都能快速把题面拆解成代码。你可以把每道BFS题按这四步在纸上写一遍思路清晰了再动手码字错误率会大幅下降。4.2 剪枝与去重避免死循环的核心BFS里最容易爆的两个问题一个是死循环一个是重复扩展。根源都是一个没有正确去重。死循环的场景很常见比如在迷宫里走格子如果你没有visited节点会在两个格子之间来回移动队列永远空不了。哪怕你记得标记visited标记时机不对也会导致重复节点大量堆积。我见过最典型的错误是在pop的时候才标记visited这样同一层扩展时同一个节点可能被多个邻居重复入队三次、四次队列以指数速度膨胀。剪枝是和去重一起考虑的。所谓剪枝就是在生成邻居之前先判断某些方向“没有意义”或者“不可能到达答案”把它们直接砍掉。比如迷宫题里如果你已经知道终点和当前位置的相对方向就可以优先走朝向终点的方向。这种启发式策略不会改变最坏复杂度但在平均情况下能省不少时间。另外一种常见剪枝是把“不可达区域”提前排除。比如在迷宫题里如果起点和终点都是0但整张图不连通BFS自然会返回-1但如果在BFS前用并查集或者简单的连通性判断先排除一部分可以省去大量无意义的搜索。不过要注意这属于工程优化面试时先保证AC再谈优化。4.3 位运算与状态压缩实战当状态是棋盘、网格或者是一个小组状态时直接用二维数组表示会很费内存而且作为visited的键也很麻烦。我强烈建议你掌握两种状态压缩方式。第一种是“序列化为字符串”。比如八数码问题棋盘有3乘3个格子你直接把每行拼起来变成一个9位字符串比如123456780。然后visited直接用set存字符串BFS扩展时再把字符串切回去操作。这种方式代码简单虽然运行效率略低但99%的题目都够用。第二种是“用整数位掩码”。比如状态是若干格子是否被占用一个int的每一位就代表一个格子。经典的应用是旅行商问题TSP的BFS/DP版本用一个整数mask表示已访问城市的集合再用另一个维度表示当前所在城市。这种方式速度极快但需要你对位运算比较熟。写位运算时我有两个坑要提醒。一是括号问题(mask | (1 city))一定要加括号因为Python的位运算优先级比较低。二是从低位开始编号习惯约定城市0对应第0位不然容易错位。如果你刷LeetCode 847“访问所有节点的最短路径”就会明白这种状态压缩有多重要。那道题里状态是“当前节点 已访问节点集合”用(node, mask)做visited的键BFS自然就出来了。第一次看到这种题可能懵但掌握了位掩码之后你会发现它就是BFS模板的一个变体。4.4 复杂度分析与参数选择面试时讲完BFS解法面试官一定会追问“复杂度是多少”这个要能稳稳答出来。标准结论是BFS的时间复杂度为O(VE)其中V是节点总数E是边总数。网格题里VmnE大约等于4mn四方向所以复杂度就是O(mn)。单词接龙题里如果用模式映射生成邻居Vn每个单词生成O(L26)个邻居所以复杂度是O(nL26)这比O(n^2L)好太多。空间复杂度主要看队列和visited。visited存储所有已访问状态最坏是O(V)队列存储当前层的节点数最坏在网格里是O(mn)在状态空间题里可能接近O(V)。双向BFS的空间是两侧的visited相加通常远小于单向BFS。关于参数选择我一般会用两个判断标准第一如果V小于等于10的5次方queue和set直接上不用优化。第二如果V很大优先尝试状态压缩降低单状态占用内存再考虑双向BFS减少搜索量。记住一个心法先写出正确的BFS再优化不要在优化中把正确性搞丢。5. 常见问题与排查技巧实录5.1 队列里到底存什么很多新手纠结“队列里应该放坐标还是放坐标步数”。我的建议是优先用分层循环也就是队列只存状态步数通过层次来统计。这样能避免一个隐藏bug如果你在节点里带step字段两个不同路径到达同一个状态时step可能不一样你还需要额外比较大小逻辑就复杂了。但有些场景确实需要在队列里存额外信息比如带方向状态、带钥匙状态、带剩余步数。这时候我会用一个元组比如(x, y, dir, steps)或者定义一个小的数据类。只要visited的键包含所有关键状态维度就行。举个例子LeetCode 864“获取所有钥匙的最短路径”状态是当前位置和已收集钥匙的掩码队列里就直接存(x, y, mask)step用分层循环统计而不是存在队列里。这样逻辑清晰也不会混淆同一状态下不同路径的步数。5.2 什么时候用visited几乎所有的BFS都需要visited只有一种情况可以不用你明确知道搜索图是一棵树不会出现环。比如二叉树层序遍历天然没有环不需要visited。但网格图、状态图可能存在环必须有visited。还有一个容易被忽略的点visited的键必须和状态定义完全匹配。比如你在迷宫题里只考虑坐标那就漏掉了“方向不同”这个维度但在有方向限制的题里比如机器人只能转弯不能后退就必须把方向也放进visited。我调试过的一个案例是LeetCode 994“腐烂的橘子”如果只记录坐标visited不记录天数会出现在同一轮感染过程中同一个橘子被多次设置为腐烂导致新鲜橘子计数错误。所以visited不仅要回答“这个状态访问过没有”还要在你需要时能区分“是哪一轮访问的”。5.3 为什么TLE刷BFS最烦的就是“代码看着没问题一跑TLE”。我总结过几个高频原因按出现频率排序第一个visited标记晚了。前面反复强调过等到出队再标记会导致大量重复入队队列膨胀到爆炸。这个bug肉眼很难发现因为数据小的时候一切正常一旦数据量上来就瞬间爆炸。建议所有BFS都养成“入队即标记”的习惯。第二个生成邻居太慢。比如单词接龙里用两两比较生成邻居O(n^2*L)直接超时。我一般会先估算最坏情况如果V超过几千就要考虑用模式映射或者预计算来加速。第三个状态表示过于昂贵。如果你用一个二维数组代表棋盘然后直接把整个数组作为visited的键每次比较和哈希的开销都很大。改成字符串或整数后效率能提升一个量级。第四个没有剪枝就盲目遍历。有些题有很明显的剪枝条件比如只允许向右和向下走如果忘了剪枝BFS会去尝试所有方向浪费大量时间。5.4 内存爆炸的排查TLE之外BFS还容易MLE。MLE通常是因为队列或者visited存了太多状态。排查思路很简单先估计状态总数V是多少。如果V是10的6次方量级又是Pythonset和deque会很占内存你就要考虑用数组代替set或者用状态压缩。比如网格题visited完全可以用一个布尔二维数组没必要用set。如果是状态空间题能压缩成int就压缩成int。另一个有效手段是双向BFS。状态空间指数增长时单向BFS的队列可能存了整层几十万个节点双向BFS因为只扩展一半深度内存占用会少很多。以“单词接龙”为例我实测用单向BFS峰值内存可能到数百MB双向BFS能压到几十MB。启动排查的时候我习惯在代码临时加一行print(len(q))跑一遍样例看队列长度增长趋势。如果增长是指数型的说明搜索空间太大必须考虑优化方案。5.5 高频易错点速查表刷得多了我把高频易错点整理成一张表每次写完BFS都会对照检查一遍。易错点典型场景解决办法起点等于终点时返回错误矩阵题起点和终点同一个格子开始前先判断start target越界检查顺序颠倒先访问数组再判断越界先判断坐标是否在界内再取数组值visited标记过晚出队时才标记pop之后立刻标记或入队时标记分层时忘记固定size队列长度在循环中变化用size len(q)固定当前层节点数多源初始化遗漏腐烂的橘子所有腐烂起点没都入队初始遍历全图把所有源节点加入队列状态转移少方向八方向题只写上下左右读题后明确方向数量写全方向数组对题目边界条件不敏感n为1时答案应该是1提前处理特殊输入这张表不敢说覆盖所有坑但基本把我在刷题群和面试中看到的高频bug都列进去了。写完代码以后对表自查能省很多次提交。6. 实战中的思考方式6.1 如何快速判断一道题是BFS判断一道题是不是BFS其实有非常强的信号词。看到“最少步数”“最短路径”“最小操作次数”“最少转换次数”这类表述就要马上警觉。看到“扩散”“感染”“传播”“逐层”“所有可能”这类词也常常意味着BFS。多维状态移动类的题比如“重新安排行程”虽然不一定用BFS但分析路径时也可以先从BFS入手。我判断时还会再问自己一个问题这个搜索图是“无权图”吗如果每一步代价一样BFS就是最佳选择如果代价不同就转Dijkstra。这个判断比单纯找信号词更可靠因为它直接对应算法理论。有时候题目没说“最短”但场景本质是“逐层扩散”比如“多久能感染所有人”其实还是BFS。有一个反直觉的点你可能会遇到有些题表面上要求“最小代价”但代价始终是1比如“按钮只有开和关两种状态每次按一下代价1”那本质仍是无权图BFS照用不误。6.2 从AC到优化面试怎么加分能AC只是及格面试的时候想加分你还要展现优化意识。我会在讲完基础BFS以后主动补上这几点。第一点指出当前算法的时间和空间复杂度。这是基本功但很多人面试时不说等面试官问才被动回答体验差很多。第二点讲清楚双向BFS的适用条件。如果目标是明确的单一状态我会补一句“这个题可以用双向BFS优化因为起点和目标都已知”。这种主动优化的表达面试官会很受用。第三点如果题目允许可以提A搜索。A在BFS的基础上引入启发式函数能更快地朝目标扩展。比如八数码问题用“曼哈顿距离之和”作为启发式函数效果立竿见影。不过面试时别一上来就写A*基础BFS能AC之后再提优化会比较稳妥。我自己的经验是面试官考察BFS往往不是看你背得多熟而是看你有没有“状态图”的抽象能力和“复杂度可控”的工程意识。能在白板上把状态转移画清楚比手速敲代码重要得多。6.3 几个值得练的进阶题最后推荐几个我刷过之后觉得收获很大的题按照难度递增排列你可以用来检验自己是否真的掌握了BFS。LeetCode 994“腐烂的橘子”是入门多源BFS的必备题。LeetCode 127“单词接龙”训练隐式图和双向BFS。LeetCode 752“打开转盘锁”训练状态设计和字符串处理。LeetCode 773“滑动谜题”训练将二维数组压缩为字符串并做BFS。LeetCode 847“访问所有节点的最短路径”训练位掩码状态压缩。LeetCode 864“获取所有钥匙的最短路径”则是多维状态BFS的综合题难度较高但做完会特别有成就感。我个人的练习方法是每道题先自己写一版BFSAC之后再看题解区的高票代码重点看别人的visited设计和邻居生成方式。很多高票解法的差异就在这两处每次都能学到新技巧。踩过几次坑之后我最大的体会是BFS题能不能快速做出来不取决于你背了多少模板而取决于你能不能把一个实际问题转成“节点-边-visited”的状态图。这个转换能力一旦练成路径搜索类的高频题基本就是送分题了。希望这篇梳理能帮你少走点弯路刷题的时候如果遇到新的BFS题目也欢迎拿我的“四步法”套一套大概率比你自己硬想快很多。