上一篇我们把 BFS 的基础模板讲透了一个队列、一张 visited 表、按层向外扩散这套组合拳用来处理网格迷宫、二叉树层序遍历已经够用。但真正在实际竞赛、面试和工程里用 BFS大多数人的体验是模板会背题目一变就懵。这篇下我不打算再重复模板而是把那些模板背后真正值钱的东西拿出来聊——变体怎么选、和 DFS 比到底差在哪、为什么很多人最后会从 BFS 转向 A*、以及我自己写 BFS 踩过的几个坑。这些内容不管你是刷题党、算法竞赛选手还是要在游戏 AI、地图导航、依赖调度里实际落地的工程师应该都能用上。1. BFS的三种高频变体解决模板能跑但不好使的问题基础 BFS 的核心是一个队列加标记数组但它有一个很大的软肋如果状态空间比较大盲目地按层扩散会迅速耗尽内存和时间。很多看似用了 BFS 却超时的题目其实不是 BFS 不对而是你没用对变体。1.1 双向BFS明确起点和终点时搜索空间能砍掉一半以上双向 BFS 的思路特别朴素既然起点和终点都知道为什么非要一个方向愣头愣脑地往外扩让两个方向同时扩各自走到一半再碰头不就行了这看起来只是两个队列一起跑但背后的复杂度收益是指数级的。假设每个节点平均有 b 个邻居目标距离是 d 层单向 BFS 在最坏情况下要访问大约 b^d 个节点。双向 BFS 让两边各走大约 d/2 层两边合计访问约 2 * b^(d/2) 个节点。当 b 和 d 都不小的时候这个差距不是省了一半时间而是把跑不动变成轻松跑完。from collections import deque def bidirectional_bfs(start, target, neighbors): if start target: return 0 q_start deque([start]) q_target deque([target]) dist_start {start: 0} dist_target {target: 0} while q_start and q_target: # 每次只扩展节点数较少的那一侧保持两侧规模均衡 if len(q_start) len(q_target): cur q_start.popleft() for nxt in neighbors(cur): if nxt not in dist_start: if nxt in dist_target: return dist_start[cur] 1 dist_target[nxt] dist_start[nxt] dist_start[cur] 1 q_start.append(nxt) else: cur q_target.popleft() for nxt in neighbors(cur): if nxt not in dist_target: if nxt in dist_start: return dist_start[nxt] 1 dist_target[cur] dist_target[nxt] dist_target[cur] 1 q_target.append(nxt) return -1这里有一个细节值得多说一句双向 BFS 的停止条件不是某一侧队列空了而是另一侧的某个节点已经被这一侧访问到。所以两边都要维护自己的 visited 表并且每次选择节点数更少的一侧去扩展这个优化能明显减少总扩展量。我见过不少人在这个边界条件上写错结果退化成单向 BFS 甚至死循环。适用场景也很明确最少步数类问题比如单词接龙、走迷宫、打开转盘锁。这类题只要起点和终点都明确双向 BFS 基本是标准答案。但如果你连目标状态都不确定就别硬套了。1.2 多源BFS处理多个着火点同时扩散的思维转换另一类高频变体是多源 BFS。典型题目就是腐烂的橘子一开始有多个腐烂橘子每分钟向周围四个方向传染新鲜橘子问多久全部腐烂。最直觉的做法是对每个腐烂橘子分别做一次 BFS再把结果叠加取最小值。这个思路没错但复杂度很容易爆炸如果腐烂橘子有 k 个每次 BFS 是 O(n*m)整体就是 O(k*n*m)一旦 k 接近 n*m这代码基本告别 AC 了。正确的打开方式是建立一个虚拟超级源点把它和所有初始源点连起来边权为 0然后只跑一次 BFS。实现上不需要真的建这个虚拟节点直接把所有源点的距离初始化为 0 并一次性入队即可from collections import deque def multi_source_bfs(grid, sources): m, n len(grid), len(grid[0]) dist [[-1] * n for _ in range(m)] q deque() for x, y in sources: dist[x][y] 0 q.append((x, y)) dirs [(1, 0), (-1, 0), (0, 1), (0, -1)] while q: x, y q.popleft() for dx, dy in dirs: nx, ny x dx, y dy if 0 nx m and 0 ny n and dist[nx][ny] -1: dist[nx][ny] dist[x][y] 1 q.append((nx, ny)) return dist这个技巧的关键在于理解 BFS 的按层扩散和同时到达之间的关系。所有源点同时开始扩散谁先到达某个格子谁就赋予该格子最短距离。如果某个格子的 dist 已经被更新说明它已经归属于某个更近的源后续到达的源即便路径合法距离也只会更大没有更新必要。多源 BFS 在现代地图、社交网络场景里也经常出现比如定位多个门店到周边用户的最短可达时间、多台服务器向网络内广播消息的延迟计算。它本质上是在算距离我最近的源点距离是多少。1.3 状态压缩BFS当坐标不再起作用状态是整个棋盘第三种进阶用法是当你处理的根本不是一个二维网格而是一个局面。华容道、八数码、推箱子这类益智游戏BFS 的每个节点是整个棋盘状态而不是某个格子。这种题的难点不在 BFS 本身而在状态编码。以八数码为例3x3 棋盘上有 8 个数和一个空位棋盘的一种排列就是一个状态。你可以把它拼成一个 9 字符的字符串比如 123456780然后用一个set去重也可以直接用整数按位压缩速度更快但代码更绕。from collections import deque def sliding_puzzle(board): start .join(str(x) for row in board for x in row) target 123450 if start target: return 0 # 0 所在位置可以交换的下标 moves {0: [1, 3], 1: [0, 2, 4], 2: [1, 5], 3: [0, 4], 4: [1, 3, 5], 5: [2, 4]} q deque([(start, 0)]) seen {start} while q: state, step q.popleft() if state target: return step zero state.index(0) lst list(state) for nxt in moves[zero]: new_lst lst[:] new_lst[zero], new_lst[nxt] new_lst[nxt], new_lst[zero] new_state .join(new_lst) if new_state not in seen: seen.add(new_state) q.append((new_state, step 1)) return -1写这类 BFS 时最容易忽略的是编码/解码必须配套。你用字符串做 visited那每次扩展都要做一次列表到字符串的转换你用整数位运算压缩就必须保证每个状态的编码唯一。这些转换影响很大因为状态空间可能达到几十万甚至上百万级别一次转换多花 10ms几百个状态叠加就可能超时。状态压缩 BFS 我放到这一节是因为它往往和后面要讲的 A* 一起出现——八数码就是你体会 A* 到底比 BFS 聪明多少的绝佳试验田。2. BFS和DFS为什么总被放在一起比较任何一个学过搜索的人几乎都会遇到DFS 还是 BFS的选择题。网上资料喜欢用迷宫找出口举例但实际用起来比这复杂因为两者的差异不止是一个用栈一个用队列。2.1 搜索策略的根本差异一个对目标敏感一个对目标不敏感DFS 的策略是一条路走到黑走不通就回头它优先把一条路径尽量探深直到叶子节点或死路。BFS 的策略是以起点为圆心一层一层向外扫描它优先确认距离起点最近的所有节点。这个差异带来一个很重要的推论BFS 对目标在第几层这件事极其敏感它必须把目标所在层之前的每一层全部展开才能到达目标DFS 则完全看运气如果一条分支深处恰好藏着目标DFS 可能几个递归就找到了如果目标在一个很偏的分支DFS 可能几乎遍历了整棵树才碰巧到达。在算法竞赛里DFS 常配剪枝来弥补运气不好的缺陷。比如可行性剪枝、最优性剪枝让不可能通向目标的子树尽早被砍掉。而 BFS 很少能靠剪枝大幅提速因为它的扩展顺序由距离决定不太好提前判断哪一层里的哪些节点值得略过。所以简单粗暴地总结要保证最短路径BFS 是唯一不需要额外条件就能做到的DFS 如果要找最短路径得全程记录并比较所有可行路径的长度成本极高。2.2 空间复杂度BFS 软肋和 DFS 的底气BFS 的空间占用是它最大的软肋。设分支因子为 b深度为 dBFS 在探索最后一层之前队列里最多会堆积 b^d 量级的节点。对于深度为 30 的满二叉树单向 BFS 队尾可能堆着上亿个节点内存直接爆炸。DFS 只需要保存当前路径上的节点空间消耗是 O(d)递归版还有系统栈的开销。同样是深度 30DFS 的栈深也就 30 层左右对比非常悬殊。很多初学者以为BFS 肯定比 DFS 快其实是在迷宫小地图上得出的错觉。一旦状态空间变大BFS 首先遭遇的不是速度问题而是空间问题还没开始比谁快内存已经先撑不住了。这也是为什么很多大规模搜索问题会退回 DFS 剪枝或者转而用迭代加深 DFSIDDFS——它用多次重复搜索的代价换取 O(d) 空间去实现 BFS 的逐层加深效果。2.3 什么时候必须 BFS什么时候 DFS 更顺手判断标准说白了只有几个问题要求最少步数最短距离最快扩散时间优先 BFS。问题要求有多少种路径给出所有排列组合判断连通性DFS 通常更自然。问题里状态空间极大、必须依靠剪枝缩小范围DFS 剪枝往往是主力。问题需要访问树/图的每个节点并输出某种有序遍历结果两者都能做看遍历顺序要求。拿树的遍历举例前序、中序、后序天然是 DFS 的领域因为递归函数和系统栈一配代码短得可怜。层序遍历则是 BFS 的看家本领因为它就是要你按深度一层一层输出。2.4 递归与迭代一个容易被严重低估的工程问题DFS 在工程里经常写成递归代码非常简洁但递归深度一旦超过阈值就会爆系统栈这个不是算法错而是运行时限制。比如深度 10 万层的 DFS在 Python 里默认递归深度只有 1000 左右直接RecursionError。这时候要么把递归改成显式栈要么用迭代加深。BFS 因为天生是迭代写法几乎不会遇到函数调用栈爆掉的问题。这其实也是很多大规模图遍历题默认推荐 BFS 的原因之一它不只是正确率和时间靠谱工程实现上也很稳不需要调递归深度上限。3. BFS不只是走格子三类你可能没意识到的BFS应用如果你只把 BFS 当成网格里走最短路径的专用算法那真的亏大了。BFS 的底层模型是状态即节点、转移即边只要满足这两个条件任何问题都能图化然后就有 BFS 的用武之地。3.1 隐式图建模从地图到抽象状态空间所谓隐式图就是我们不用真的建一个邻接表而是根据规则在需要时动态生成邻居。前面提到的八数码就是这么干的它的每个状态是棋盘排列转移规则是空位和上下左右交换。这类问题太多了。比如最少多少次操作能把字符串 A 变成字符串 B每次只能改一个字符且中间结果必须在字典里把每个单词看成状态、每次修改看成边这就是一个典型的隐式图 BFS。再看最少用几枚硬币凑出 target 金额把当前金额作为状态每次加一枚硬币到达新状态从 0 元到 target 元做 BFS也是合法解。建模这个动作比写 BFS 本身难得多。我见过很多人看到倒水问题华容道推箱子被吓住但只要你先问自己三个问题题目就开始解构了一个状态最少需要哪些信息才能完整描述从这个状态出发有哪些合法操作每次操作到达什么新状态如何判断两个状态是否相同去重方式三问回答完毕剩下的就是套模板。3.2 层序遍历思想从二叉树到扩散类业务逻辑二叉树层序遍历是 BFS 最直观的形态但按层处理这件事在系统设计里更值得玩味。社交网络里的查找 N 度联系人、内容平台的传播层级统计、支付风控里的关联交易网络扩散本质上都依赖逐层向外扩展。在这些系统里层号往往直接对应某种业务含义网络传播里代表转发次数权限系统里代表授权深度供应链里代表配送周转环节。BFS 在这里的优势是你天然知道每个节点在第几层到达这个信息在业务上通常就是关键指标。举个具体的工程例子一个简单的反作弊需求是找出某账号的朋友、朋友的朋友、朋友的朋友的朋友中有多少个被标记为风险账号。这完全就是一个限制最大扩展层数的 BFS每次从队列弹出节点时就检查当前层号超过 3 层就停止扩展。把 visited 换成风险账号集合来剪枝就能在大量关系数据里快速得到答案。3.3 拓扑排序BFS 的另一个名字叫 Kahn 算法很多人没意识到拓扑排序里最经典的 Kahn 算法就是 BFS。它的步骤是找所有入度为 0 的节点入队出队时解除对邻居的约束邻居入度降到 0 就继续入队。这就是一个按依赖关系逐层剥洋葱的过程剥出来的顺序就是一个合法的拓扑序。from collections import deque def topo_sort(n, edges): indegree [0] * n adj [[] for _ in range(n)] for u, v in edges: adj[u].append(v) indegree[v] 1 q deque([i for i in range(n) if indegree[i] 0]) result [] while q: u q.popleft() result.append(u) for v in adj[u]: indegree[v] - 1 if indegree[v] 0: q.append(v) return result if len(result) n else []这里 BFS 的队列装的不是普通节点而是当前没有前置依赖的节点。它在课程表排课、Maven/Gradle 依赖解析、编译器模块依赖分析、构建系统任务调度里都是底层算法。如果想在多个合法拓扑序里挑字典序最小的那个只要把普通队列换成优先队列每次弹出编号最小的入度零节点即可。这个细节在面试里经常被问本质上就是给 BFS 的队列换了一种排序策略。4. BFS与A*的优缺点什么时候该放弃BFS去用启发式搜索讲到这里BFS 的通用性和灵活性已经够强了但它有一个绕不开的问题它不在乎目标在哪。就像地震波从震源向四面八方均匀扩散哪怕目标就在正前方 100 米它也照样把左边、右边、后边的区域扫一遍。A* 算法就是为了解决这个浪费而生的。4.1 从BFS到A*核心是给节点加一个方向感A* 在 BFS 的基础上引入了一个估价函数f(n) g(n) h(n)g(n) 是从起点到当前节点 n 已经付出的真实代价h(n) 是从 n 到目标节点的估计代价。A* 每次从优先队列里取出 f 值最小的节点来扩展而不是像 BFS 那样严格按 g 值分层。h(n) 是启发函数它的质量决定 A* 的行为当 h(n)0 时A* 退化成 Dijkstra也就是一种加权 BFS不再有任何方向感。当 h(n) 不超过真实代价时A* 保证找到最优解此时称为可采纳启发。当 h(n) 越接近真实代价扩展的节点数越少搜索越快。在网格类问题里最常用的 h(n) 是曼哈顿距离和欧几里得距离。曼哈顿距离适合只能上下左右移动的场景因为它本身就是四方向移动的真实代价下限如果允许斜着走欧几里得距离更贴近真实代价但它往往会低估导致扩展节点偏多。这个细节很多入门玩家会忽略直接导致 A* 效果不佳然后回头骂 A* 没用其实是启发函数选错了。4.2 BFS vs A*优缺点对比与适用边界对比维度BFSA*实现复杂度低队列加 visited 即可较高优先队列 g/h 更新逻辑方向感无向所有方向均匀扩展有偏向目标方向扩展最短路径保证能保证无权图启发函数可采纳时能保证空间占用高按层堆积节点相对更低扩展节点少启发函数要求不需要必须设计直接影响效果适用场景无权图、状态简单、目标不明确状态空间大、目标明确、有地图暗示做一个直观对比在一张 100x100 的网格上从左上角走到右下角如果中间没有太多障碍BFS 大概会把半个地图都扫一圈才能摸到右下角。A* 用曼哈顿距离做启发会把搜索范围收缩在一条很窄的走廊内扩展的节点数可能只有 BFS 的十分之一甚至更少。但 BFS 也有它的绝对优势不依赖目标这个信息。有些问题根本说不清目标大概在哪比如求连通块数量、求所有节点到最近源点的距离目标不是一个点而是分布在整个空间里的属性A* 反而没有用武之地。换句话说A* 是目标明确的单目标寻路利器BFS 是大规模扩散与标记的通用底座两者并不是简单的替代关系。4.3 用八数码实测三种搜索策略的扩展量差异我拿八数码做过很多次对比测试现象非常典型。从一个打乱的初始状态出发寻找目标状态123456780纯 BFS 盲目按层扩展随机实例往往要展开几千到数万甚至十几万个状态步数一长就非常吃力。朴素 DFS不做任何剪枝可能很快命中也可能在一个错误分支里钻进死胡同扩展量极不稳定。A* 用曼哈顿距离总和作为启发函数通常只需要展开几十到几百个状态就能找到解差距可达一两个数量级。这不是说 A* 一定比 BFS 好而是想说明一个问题当你能直观估算当前状态距离目标有多远时A* 就是 BFS 的高效升级版当你连这个估价函数都设计不出来时就别硬上 A*老老实实 BFS 反而更稳。工程上还有一个常见的折中方案叫迭代加深 BFSIDDFS它反复用 DFS 模拟 BFS 的逐层扩展空间占用只有 O(d)时间会稍慢但可控。在内存受限的嵌入式或游戏 AI 场景里这种牺牲时间换空间的思路很有价值。5. 写BFS最常见的5类坑以及我的处理方案BFS 模板看似简单但真正刷题和上线跑的时候踩坑点比想象中多。下面这些基本都是我实际遇到并排查过的逐个说清楚。5.1 入队时标记visited还是出队时标记这个问题能让你TLE这是 BFS 新手最经典的错误在从队列弹出节点时才标记 visited。表面上看起来没问题但仔细算一笔账后会发现同一个节点可能被多个邻居重复入队。在网格题里这意味着队列长度成倍膨胀如果图结构再稍微复杂一点直接超时或者内存溢出。正确做法是在把邻居入队的那一刻就标记 visited保证每个节点最多被推入队列一次。以最短距离为例我推荐的模板是直接用 dist 数组充当 visitedfrom collections import deque def bfs_distance(graph, start): dist [-1] * len(graph) dist[start] 0 q deque([start]) while q: u q.popleft() for v in graph[u]: if dist[v] -1: dist[v] dist[u] 1 q.append(v) return dist这里dist[v] -1就是未访问的标记第一次访问时写入的距离天然就是最短距离。因为 BFS 的层序性质决定了某个节点第一次被访问到的那一跳一定是从起点出发的最短路径后续再被其他路径访问到距离只会更长无需更新。5.2 邻接表存图时重边会在不经意间爆掉队列用邻接表存图时如果不去重同一个邻居可能出现在多条边里BFS 会把它重复入队多次。虽然 visited 能在弹出时拦截但它已经白白占过队列位置了。数据量大时重边带来的膨胀非常可观。我的习惯是建图阶段就完成去重用set类型的邻接表或者在插入边时做一次检查。不要等到 BFS 过程中去判重那样虽然也能保证正确但每次都多做一次in判断开销不低。5.3 只用 bool visited 会丢失距离信息很多人习惯开一个bool数组visited然后在 BFS 里再用一个全局变量ans来统计层数。这个做法在简单的二叉树层序遍历里勉强能行但一旦出现需要知道每个节点最短距离的需求就非常容易出错尤其当队列里同时存在不同层的节点时靠一个计数器很难精确对应每个节点。直接开 dist 数组是更稳的写法在状态压缩 BFS 里则用字典或set记录状态与步数比如{(state, step)}。原则是把距离和访问状态合并成一个结构别让它们分离否则你对不上号。5.4 大矩阵的坐标压榨能省就省在 2000x2000 级别的网格上做 BFS一个坐标为 (x, y) 的tuple偶尔没事但如果访问了上百万个格子tuple 的创建开销会非常明显。笔试和竞赛里我常见到两种优化把二维坐标转换成一维整数id x * cols y出队后再x id // cols; y id % cols还原。开四个方向数组dx [1, -1, 0, 0]、dy [0, 0, 1, -1]用 for 循环逐个访问减少重复代码。这两条看着不起眼但在 LeetCode 的硬核用例或 ACM 的边角数据上常常就是卡线过和TLE的分水岭。5.5 双向BFS和多源BFS的边界细节写乱了别怪算法双向 BFS 最容易写乱的是停止条件和交替扩展两部分。停止条件不是某一侧队列空而是扩展时发现新邻居已经在另一侧的 visited 里交替扩展也不是严格左一步右一步而是每次选择当前节点数更少的一侧扩展这样能有效防止一侧爆炸。多源 BFS 最容易踩的坑是对每个源点分别做一次 BFS。如果是 k 个源点这等于把复杂度乘了 k 倍非常致命。正确做法是把所有源点初始距离设为 0 并入队只跑一次 BFS。只要理解所有源点同时以 0 开始扩散这个虚拟超级源点模型就不会再犯这个错。写了这么多年 BFS我现在拿到一个搜索题会先问自己四个问题目标状态是什么、状态怎么编码、每一步有哪些合法转移、我能不能估算当前距离目标多远。这四个问题的答案基本决定了我用朴素 BFS、双向 BFS、多源 BFS 还是 A*。如果你刚把 BFS 的基础模板学完我建议你接下来做两件事一是把上面几个变体各找两三道题练熟尤其注意把入队标记、dist 数组、状态编码这几个基本功刻进肌肉记忆二是去研究一下 A* 和迭代加深它们会让你对搜索的理解从会背模板上升到会设计搜索策略。BFS 的价值不只在于那些一眼就要求最短路径的题目更在于它教会你一种构建状态空间、按层推进、去重收敛的思维模型。把这个模型吃透了后面学图论、动态规划、系统设计都会顺很多。