去年把 BFS 基础模板和经典题型整理出来之后一直有读者催更能不能讲讲 BFS 的变种双向 BFS、0-1 BFS、多源 BFS 到底怎么用和 DFS、A* 算法相比BFS 算法到底赢在哪、输在哪这次我一口气把这些内容补齐相当于 BFS 专题的下半篇。如果你还没看过基础部分也不影响阅读这篇会把每个变种从原理到代码完整过一遍。这篇文章的核心定位是把 BFS 从“会写模板”带到“会选方案”的阶段。我见过太多人拿到题目第一反应就是套模板结果要么状态空间太大直接超时要么边权不统一模板根本处理不了。所以这篇不仅讲每个变种怎么实现更重要的是讲清楚什么时候该用哪个以及不同方案之间的取舍逻辑。适合刚学完基础 BFS 想进阶的算法学习者也适合准备面试、竞赛前系统梳理的人。1. BFS 的边界在哪里从基础框架到实战变种1.1 基础 BFS 的核心逻辑回顾在展开变种之前有必要先把基础 BFS 的框架再压实一遍。BFS 算法的本质是逐层扩展从起点出发先访问所有距离为 1 的节点再访问距离为 2 的节点以此类推。这种“按层推进”的特性决定了它在无权图上天然能找到最短路径这是 DFS 做不到的。from collections import deque def bfs(start, target, neighbors): if start target: return 0 queue deque([start]) visited {start: 0} while queue: cur queue.popleft() for nxt in neighbors(cur): if nxt in visited: continue if nxt target: return visited[cur] 1 visited[nxt] visited[cur] 1 queue.append(nxt) return -1这段代码看起来简单但里面藏着几个容易被忽略的关键点visited 要在入队时标记而不是出队时标记否则同一个节点会被重复入队多次返回值是 visited[cur] 1 而不是在循环外面统一加一因为 BFS 的层数是从起点开始累计的。这些细节在基础篇讲过这里不再展开但接下来的所有变种本质上都是在这个框架上做调整。1.2 基础框架的三个局限基础 BFS 能解决很多问题但实战中你一定会遇到三类情况让这个模板直接失灵。第一类是状态空间爆炸。假设每个节点有 3 个邻居搜索 10 层就要访问 3 的 10 次方个节点约 5.9 万个搜索 20 层就是 3 的 20 次方约 34 亿个。很多真实场景下单向 BFS 还没搜到目标就已经超时超内存了。这时候需要双向 BFS让搜索空间从指数级降到指数级的一半量级。第二类是边权不统一。基础 BFS 假设每条边的代价都是 1但现实中可能有“走普通路耗时 1、走捷径耗时 0”的情况。如果直接把边权为 0 的边也按普通 BFS 处理最短路径就会被算错。这时候需要 0-1 BFS 或者 Dijkstra 算法来处理。第三类是起点不唯一。比如迷宫里有多个出口或者地图上有多个感染源同时扩散。如果对每个起点分别做一次 BFS时间复杂度就是 起点数 × 单次 BFS 的代价很容易超时。这时候需要用多源 BFS把所有起点打包成同一层一起扩展。这三类问题正好对应了双向 BFS、0-1 BFS、多源 BFS 三个核心变种。接下来逐个拆解原理和实现。2. 核心细节解析与实操要点2.1 双向 BFS让搜索空间指数级收缩双向 BFS 的思路一句话就能说清既然从起点往终点搜要扩展很多层那就同时从终点往起点搜两边在中途相遇。这样做为什么快数学上可以直接算出来。假设搜索树的分支因子是 b目标深度是 d单向 BFS 要访问的节点数大约是 1 b b^2 ... b^d也就是 O(b^d) 的量级。双向 BFS 让两边各搜 d/2 层两边合计访问的节点数大约是 2 × (1 b b^2 ... b^(d/2))也就是 O(b^(d/2)) 的量级。底数不变指数直接砍半这个差距是非常恐怖的。举个例子b2d30 时单向 BFS 要访问约 10 亿个节点双向 BFS 两边合计只访问约 3 千个节点差了百万倍。这就是为什么很多状态空间巨大的搜索题用单向 BFS 必超时换双向 BFS 就能过。适用条件也有讲究。双向 BFS 要求两个前提一是必须明确知道目标状态是什么二是从目标状态反向扩展是可行的。像“走迷宫从起点到终点”这种题就非常适合因为终点坐标是明确的反向走一步就是把坐标往四个方向挪一格。但如果目标状态是一个集合、无法确定唯一终点双向 BFS 就用不了。还有一种情况是反向扩展操作代价与正向不同比如某些状态转换不可逆那就只能单向搜。2.2 双向 BFS 的正确实现姿势双向 BFS 的实现有很多细节容易写错我直接给一个经过反复验证的模板然后再解释每个关键决策的原因。from collections import deque def bidirectional_bfs(start, target, 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): q_start, q_target q_target, q_start visited_start, visited_target visited_target, visited_start size len(q_start) for _ in range(size): cur q_start.popleft() for nxt in neighbors(cur): if nxt in visited_start: continue # 相遇判定 if nxt in visited_target: return visited_start[cur] 1 visited_target[nxt] visited_start[nxt] visited_start[cur] 1 q_start.append(nxt) return -1整个实现里有三个决策点每一个都是踩过坑才总结出来的。第一个决策点是“先扩展节点数少的一侧”。这样做是因为总搜索空间由两侧各自扩展的层数共同决定每次都扩小的那侧可以让两边规模保持相对均衡总体访问节点数最少。如果不做这个判断固定先扩起点侧遇到起点分支因子大、终点分支因子小的情况效率会退化得很厉害。代码里通过交换队列和 visited 字典来切换扩展侧比重新写两套逻辑要简洁得多。第二个决策点是“相遇判定必须在新节点产生时立刻判断”。很多人会把判断写在从队列弹出节点的时候这样也能得到正确答案但会让队列里多存一批无用的节点——因为相遇可能在这一层的前半段就已经发生了后面弹出的节点都是多余的。在产生新节点 nxt 时立刻判断它是否在另一侧的 visited 里能第一时间返回结果减少无效扩展。第三个决策点是两侧的距离计算方式。注意相遇时返回的是 visited_start[cur] 1 visited_target[nxt]其中 visited_start[cur] 是 cur 到起点的距离visited_target[nxt] 是 nxt 到终点的距离中间的 1 是 cur 到 nxt 这条边的代价。这个公式很容易写错常见的错误是写成 visited_start[nxt] visited_target[nxt] 或者其他组合结果差一。我建议把 visited 字典的语义固定为“节点到当前侧起点的距离”这样每次相遇时直接用两边已知距离相加再补上当前边的 1就不会乱。2.3 0-1 BFS当边权不再是 1基础 BFS 只能处理边权都为 1 的情况。如果图里边的权重只有 0 和 1 两种值直接用 Dijkstra 有点浪费因为 Dijkstra 需要优先队列复杂度是 O(E log V)而 0-1 BFS 能把复杂度压到 O(V E)做法就是用双端队列代替普通队列。核心逻辑是从队列中取出节点 u 后遍历它的所有邻居 v边权为 0 时把 v 从队头入队边权为 1 时从队尾入队。为什么这样是对的因为双端队列保证队列里的节点始终按照到起点的距离单调不减排列队头永远是最小距离的节点。权值为 0 的边不会增加距离所以要放到队头优先处理权值为 1 的边会在当前距离基础上加 1放到队尾就可以保持单调性。from collections import deque def bfs_01(start, end, graph): INF float(inf) dist [INF] * (len(graph) 1) dist[start] 0 dq deque([start]) while dq: u dq.popleft() for v, w in graph[u]: if dist[v] dist[u] w: dist[v] dist[u] w if w 0: dq.appendleft(v) else: dq.append(v) return dist[end]注意这里有一个和基础 BFS 不一样的地方基础 BFS 里每个节点只会入队一次因为无权图第一次访问就是最短距离但 0-1 BFS 里同一个节点可能被更新多次所以判断条件必须是 dist[v] dist[u] w 时才更新并入队而不是靠 visited 去重。这个区别很重要如果你按基础 BFS 的习惯写一个 visited 数组就会漏掉距离更新更短的路径。0-1 BFS 的典型应用场景包括迷宫中某些格子的移动代价不同、带有传送门的图搜索、以及一些状态转换问题中“保持原地”和“移动一步”两种操作的代价分别是 0 和 1 的情况。2.4 多源 BFS把多个起点打包成同一层多源 BFS 解决的问题场景是有多个起点同时开始扩散要求到达任意一个起点的最短距离或者模拟多个源头同时扩张的过程。如果对每个起点单独做 BFS时间复杂度是 O(k(VE))k 是起点数量多源 BFS 只需要做一次复杂度是 O(VE)。做法非常简单初始化队列时把所有起点都入队而不是只入队一个起点。所有起点的距离初始化为 0然后正常进行 BFS 扩展。这样第一层就是全部起点第二层是所有起点的所有邻居逐层向外推进每个节点第一次被访问时就是它到最近起点的最短距离。一个经典例子是 LeetCode 994 腐烂的橘子每个腐烂的橘子每分钟会让相邻的新鲜橘子腐烂要求计算多久能让所有橘子腐烂。如果用单源 BFS需要对每个烂橘子都跑一遍中间还要处理重叠区域非常麻烦。多源 BFS 直接把所有烂橘子入队按层扩散每一层代表一分钟扩散到的新鲜橘子就是这一分钟被感染的最后检查是否还有新鲜橘子剩余即可。另一个常见场景是“地图上多个加油站/出口求每个点到最近站点的距离”。用多源 BFS 一遍就能算完而且代码上和基础 BFS 的区别只有初始化队列那一行。3. 实操过程与核心环节实现3.1 完整案例单词接龙的双向 BFS 实现单词接龙是面试和竞赛里的高频题也是检验双向 BFS 掌握程度的好题目。题目描述是给定起始单词 beginWord、结束单词 endWord 和一个单词列表 wordList每次只能改变一个字母且改变后的单词必须在 wordList 中求从 beginWord 到 endWord 的最短转换序列长度。这道题最简单的建图方式是把每个单词看成一个节点两个单词之间如果只差一个字母就有一条边。但要注意直接把 wordList 里所有单词两两比较是否只差一个字母建图本身就是 O(n^2 × L) 的复杂度n 是单词数量L 是单词长度当 n 很大时会非常慢。更高效的做法是“按位置生成通配符”比如把 hit 分别映射为 _it、h_t、hi_再把所有共享相同通配符的单词作为邻居。但为了代码可读性下面先用逐字母替换的方式生成邻居这种方式在单词长度很短时已经足够快。from collections import deque def ladderLength(beginWord, endWord, wordList): wordSet set(wordList) if endWord not in wordSet: return 0 if beginWord endWord: return 1 q_start deque([beginWord]) q_end deque([endWord]) visited_start {beginWord: 1} visited_end {endWord: 1} def neighbors(word): res [] for i in range(len(word)): for c in abcdefghijklmnopqrstuvwxyz: if c word[i]: continue nxt word[:i] c word[i1:] if nxt in wordSet: res.append(nxt) return res while q_start and q_end: if len(q_start) len(q_end): q_start, q_end q_end, q_start visited_start, visited_end visited_end, visited_start size len(q_start) for _ in range(size): cur q_start.popleft() for nxt in neighbors(cur): if nxt in visited_start: continue if nxt in visited_end: return visited_start[cur] visited_end[nxt] visited_start[nxt] visited_start[cur] 1 q_start.append(nxt) return 0这里注意一个细节和前面通用模板不同单词接龙里的距离定义是节点的层数从 1 开始计数所以相遇时的返回值是 visited_start[cur] visited_end[nxt]而不是再加 1。因为在双方距离都是按层数计数的前提下cur 到 nxt 这条边已经被包含在 visited_start[cur] 指向的层和 visited_end[nxt] 指向的层之间了。用“从 1 开始计数”的语义来理解起点 hit 是第 1 层每次转换层数加 1当两边的层数相加时就正好是完整的转换序列长度。这里最容易出错建议读者在本地跑几个用例验证一下。3.2 超大规模搜索状态压缩与位运算技巧当 BFS 的状态不是一个普通的坐标而是一个复杂状态时直接用元组或字符串存 visited 可能非常占内存。比如八数码问题3x3 棋盘8 个数字加一个空格的状态总数是 9! 362880用字符串存没问题但如果是 4x4 的十五数码状态总数是 16! ≈ 2×10^13直接存字符串内存直接爆炸。处理办法是状态压缩。以八数码为例可以把棋盘展平成一个 9 位数字序列空格用 0 表示整个状态可以编码成一个整数。解码时通过除法和取模逐位还原这样每个状态只占一个 int 的内存同时 visited 可以用数组而不是哈希表来标记访问速度更快。def encode(board): code 0 for v in board: code code * 10 v return code def decode(code): board [0] * 9 for i in range(8, -1, -1): board[i] code % 10 code // 10 return board如果棋盘大小固定更快的压缩方式是用位运算每个数字用 4 位二进制表示9 个数字总共 36 位一个 64 位整数就能装下。解码时用掩码和移位操作比除法快一个量级。在 Java 和 C 里还能直接用数组索引模拟 visited比如开一个 136 大小的标记数组虽然有点费内存但速度极快。Python 里用 dict 或者 set 存整数编码后的状态就够了也不需要额外优化。状态压缩的核心收益是visited 的判重从哈希字符串变成整数比较内存占用大幅下降执行速度显著提升。建议所有“状态是固定大小的数组”的搜索题都优先考虑整数编码。3.3 案例延伸多源 BFS 与分层扩散的代码实现多源 BFS 的实现非常简洁这里用一个具体场景做示例给定一个二维网格其中 0 是空地、1 是障碍、2 是出口求每个格子到最近出口的距离。把所有出口作为多源起点一次 BFS 就能求出所有格子的答案。from collections import deque def nearest_exit(grid): rows, cols len(grid), len(grid[0]) dist [[-1] * cols for _ in range(rows)] queue deque() for i in range(rows): for j in range(cols): if grid[i][j] 2: dist[i][j] 0 queue.append((i, j)) directions [(1, 0), (-1, 0), (0, 1), (0, -1)] while queue: x, y queue.popleft() for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols: if grid[nx][ny] 1: # 障碍物 continue if dist[nx][ny] ! -1: continue dist[nx][ny] dist[x][y] 1 queue.append((nx, ny)) return dist这段代码里的 dist 数组同时承担了 visited 和距离记录的双重职责初始化为 -1 表示未访问。出口的 dist 是 0向外扩散一层加 1。当队列为空时所有可达格子的距离都已经算出仍然是 -1 的格子就是障碍物或不可达区域。多源 BFS 为什么只需要一次而不是对每个出口各跑一遍关键在于“同时扩展”这个动作。所有源点先入队BFS 的每一层就等价于“当前时刻所有已感染区域的边界”这样每个格子第一次被访问到的时间就是它到最近源点的最短距离。这个性质在模拟病毒传播、火灾蔓延、多中心扩散等问题里特别有用。4. BFS 与 DFS、A* 的横向对比与选型4.1 DFS 和 BFS 算法什么时候换用 DFS先看 DFS 和 BFS 的算法对比。DFS 用递归或显式栈实现BFS 用队列实现。DFS 的空间复杂度是 O(d)其中 d 是搜索深度而 BFS 的空间复杂度是 O(b^d)b 是分支因子。在搜索深度很大但目标在深层的情况下DFS 的内存占用远小于 BFS这也是递归型 DFS 在很多题目里依然是首选的原因。但 DFS 有一个天然缺陷它找到的路径不一定是最短的。因为 DFS 是沿着一条路径一路走到黑再回头换下一条路径第一次找到目标的路径完全取决于遍历邻居的顺序和最短没有关系。如果题目只要求“任意一条路径”或者“判断是否存在解”DFS 往往更快、更省内存。典型场景是判断一个图中两个点是否连通、拓扑排序、检测环、回溯类型的排列组合问题。BFS 则相反空间开销大但保证首次找到目标就是最短路径。所以选型逻辑很清晰“只要最短路径”优先 BFS“找任意解/判断连通/递归枚举”优先 DFS。还有一种常见组合是DFS 处理生成所有状态的问题BFS 处理在这些状态之间求最短路径的问题。4.2 A* 算法与 BFS 算法的优缺点对比A* 算法经常被拿来和 BFS 比较因为它们都是“从起点到目标”的搜索算法。核心区别在于BFS 是无信息搜索只知道从起点到当前节点的代价 g(n)不知道当前节点离目标还有多远A* 在 BFS 的基础上引入启发函数 h(n)用 f(n) g(n) h(n) 作为优先级排序的指标优先扩展“从起点经过当前节点再到终点”的总代价估计最小的节点。A* 相对于 BFS 的优势非常明显如果启发函数设计得好搜索效率可以比 BFS 高几个量级。比如在地图寻路中用曼哈顿距离或欧几里得距离作为启发函数A* 能直接朝目标方向扩展几乎不需要探索相反方向的区域。而 BFS 只能一圈圈向外扩散哪怕目标就在眼前也要把周围一整圈都扩展完。A* 的缺点也比较明确第一需要一个可靠的启发函数如果 h(n) 设计得不好要么搜索效率没有提升要么可能得不到最优解第二实现比 BFS 复杂需要使用优先队列每次插入、取出都有 O(log n) 的开销第三在边权全为 1 的无权图上A* 的启发函数能设计成曼哈顿距离等形式但如果图结构不规则启发函数的设计难度会明显增加此时 BFS 反而更简洁。横向对比的选型建议如果是无权图且状态规模不算太大优先 BFS简单且保证最优如果状态规模大但有明确的几何/距离信息可以利用用 A*如果图有边权且需要精确最短路径但不是 0-1 边权用 Dijkstra如果只是判断连通性或枚举解DFS 就够用。很多实际问题里BFS 和 A* 不是对立的而是可以互相补充——A* 的优先队列框架中如果 h(n) 恒为 0就退化成 Dijkstra在无权图上如果 h(n) 是可采纳的一致性启发函数效果就是带方向的 BFS。5. 常见问题与排查技巧实录5.1 队列操作与标记时机的高频坑先说我见过最多的问题visited 标记放在出队时而不是入队时。按 BFS 的层序特性同一个节点可能会从多个父节点被同时发现如果标记放在出队时队列里就会堆入大量重复节点不仅浪费内存还会让后续层的顺序混乱。正确做法是在节点入队的那一刻就标记 visited。我调试过一段代码运行结果总是正确但严重超时排查到最后就是这个问题。假设起点周围有两个节点都通向同一个节点 XX 没有在入队时标记就会在队列里出现两份。当单个节点有多个父节点时重复入队的数量会指数级增长程序性能直接从 O(VE) 退化成 O(b^d)。另一个常见问题是层数计算混乱。BFS 的层数有三种写法队列里存 (节点, 层数) 元组、用字典记录每个节点的距离、按层循环记下当前队列大小然后 for 循环处理一层。三种写法都行但混着写就会出错。我建议同一个程序里统一用 visited 字典记录距离既当标记又当距离不额外存层数代码最简洁也最不容易出错。5.2 双向 BFS 常见的终止条件陷阱双向 BFS 的终止条件是一个容易被写错的地方。很多人写成“当两个队列都为空时返回 -1”这在逻辑上没问题但问题是 BFS 的终止条件应该更早任意一个队列为空就说明这一侧已经把所有可达节点都扩展完了另一侧还没碰到它说明两侧不连通可以直接返回 -1。如果不提前终止程序会继续空转一个队列浪费时间。还有一个更隐蔽的坑相遇时返回的步数计算。我在 3.1 节已经强调过从 1 开始计数和从 0 开始计数的返回公式不同。建议所有读者在本地跑一遍“单字符替换”或“迷宫寻路”这类小规模用例亲身体验一下返回值的差别比死记公式要可靠得多。另外要多说一句双向 BFS 不是万能的。如果搜索图的深度比较浅比如层数小于 5双向 BFS 的优势不明显甚至因为维护两个队列和两个 visited 字典反而比普通 BFS 慢。所以不要盲目使用双向 BFS要基于状态空间规模判断是否值得。5.3 0-1 BFS 与多源 BFS 的易错点0-1 BFS 最典型的错误是把 visited 当成已经确定最短距离的标记只在第一次访问节点时更新距离。前面 2.3 节强调过0-1 BFS 中一个节点的距离可能被多次更新判断条件必须是 dist[v] dist[u] w而不是 visited[v] 是否存在。如果你发现代码在某些边权组合下结果不对优先检查是不是这里的问题。多源 BFS 的坑主要在距离初始化和边界条件。多源场景下所有起点的初始距离都必须是 0而不是 1。如果某个起点在网格边缘且同时是出口它的 dist 是 0向四周扩散后第一层邻居是 1以此类推。有些人会把第一个源点初始化为 1导致所有距离整体偏大 1这种错误在示例数据通过而大数据不过时特别难排查。5.4 性能优化实录从超时到 AC 的调优思路最后分享一个真实的调优过程给大家一个性能优化的参考路径。当时做的是一个大规模迷宫最短路径问题网格尺寸是 1000×1000单向 BFS 直接超时。第一轮优化把 visited 从哈希集合改成二维数组因为 Python 里 set 的开销比数组大不少这一步就砍掉了约 30% 的运行时间。第二轮优化把队列从 collections.deque 换成手写 list 模拟环形队列减少 deque 方法调用的开销又快了约 10%。第三轮优化把方向列表从“存储四元组”改成两个固定数组 dx 和 dy循环时用索引访问减少临时元组的创建。第四轮优化改成双向 BFS把搜索层数从直接搜到目标降到两边各搜一半。四轮下来最终运行时间从超时降到 200 多毫秒。这个优化顺序很有代表性先解决数据结构层面的浪费再解决算法层面的浪费。很多人一上来就直接写双向 BFS但基础的数据结构选型完全没优化结果还是慢。我的建议是先用最简单的模板跑通正确性把数据结构和语言层面的低级浪费去掉再考虑换更复杂的算法这样每一步改动都有明确的收益和目标。我在实际调试中还有一个体会BFS 的代码量不大但每个细节都能造成完全不同的性能表现。标记时机、数据类型、队列实现、方向存储这些看似琐碎的选择在极端数据下会放大成几倍甚至几十倍的差距。学习 BFS 变种的时候不要只背模板要把每个设计决策背后的原因搞清楚遇到问题才能快速定位。最后分享一个小技巧调试 BFS 时先用小规模数据把完整的扩展顺序打印出来对照手动推导的预期结果比盯着一堆错误输出猜来猜去高效得多。