1. 从单源到多源BFS的思维跃迁在算法竞赛和日常开发中广度优先搜索BFS是解决图论、网格搜索问题的基石。我们最熟悉的场景是从一个起点出发逐层向外扩散直到找到目标或遍历全图。这就像一滴墨水滴入清水波纹一圈圈散开。但现实问题往往更复杂如果同时有多个起点呢如果每一步的“代价”不同呢如果地图太大单向搜索效率太低呢这就是BFS进阶技巧的用武之地。今天我们不谈BFS的基础模板直接切入四个能显著提升你解题能力和代码效率的进阶模型多源BFS、最小步数模型、双端队列广搜和双向广搜。它们不是孤立的技巧而是针对不同问题特征的精准工具。理解它们你就能在面对诸如“多个感染源同时扩散”、“不同移动方式消耗不同”、“地图巨大搜索超时”等问题时游刃有余。接下来我会结合具体场景和代码带你逐一拆解这些技巧的核心思想、实现细节以及那些容易踩坑的地方。2. 多源BFS当“起点”不止一个传统的BFS队列初始化时只放入一个起点。多源BFS的核心思想极其简单在初始化队列时将所有起点一次性全部加入队列并正确初始化它们的距离。这样BFS的扩散过程就会从所有这些起点“同时”开始仿佛它们是一个整体源。2.1 核心思想与适用场景为什么这么做是有效的因为BFS保证了两点一是队列的先进先出FIFO特性二是当第一次访问到一个节点时距离就是最短的。当我们把所有起点同时入队它们都处于“第0层”。接下来从队列中弹出的节点无论它来自哪个原始起点BFS都会保证我们是以最小的层数即最短距离访问到新的节点。最终对于图中任意一点其距离值就是离它最近的那个起点的距离。典型场景火灾蔓延/病毒传播地图上有多个火源病毒源求每个位置被点燃感染的最早时间。最近距离场计算在网格中有多个目标点如商店、医院求地图上每个格子离最近目标点的距离。这在游戏AI寻路、图像处理距离变换中非常有用。多起点最短路径问题本质是求所有点到一组起点的最近距离而不是到一个起点的距离。2.2 实现模板与关键细节实现上与单源BFS差异很小关键在于初始化。我们以经典的“01网格中多个起点的最短距离”为例。from collections import deque def multi_source_bfs(grid, sources): :param grid: 二维网格0表示可通行1表示障碍根据题意 :param sources: 起点列表每个元素为 (x, y) :return: dist二维数组记录每个点到最近起点的距离不可达为-1 m, n len(grid), len(grid[0]) dist [[-1] * n for _ in range(m)] # 初始化为-1表示未访问 q deque() # 关键步骤多源初始化 for sx, sy in sources: if grid[sx][sy] 0: # 起点本身需合法 dist[sx][sy] 0 q.append((sx, sy)) # 标准BFS过程 directions [(0,1), (0,-1), (1,0), (-1,0)] while q: x, y q.popleft() for dx, dy in directions: nx, ny x dx, y dy # 检查边界、障碍物、是否已访问 if 0 nx m and 0 ny n and grid[nx][ny] 0 and dist[nx][ny] -1: dist[nx][ny] dist[x][y] 1 q.append((nx, ny)) return dist关键细节与避坑点距离数组初始化dist数组通常初始化为一个特殊值如-1或无穷大用于判断是否访问过。起点的距离初始化为0。起点合法性检查并非所有传入的源点都一定合法例如可能是障碍物入队前需要判断。与单源BFS的代码复用你会发现除了初始化部分后面的BFS循环和单源完全一样。这体现了多源BFS只是初始状态的不同搜索过程本身没有变化。时间复杂度依然是O(N)其中N为网格节点数。因为每个节点依然只入队、出队一次。注意多源BFS得到的是每个点到“最近起点”的距离。如果你需要知道这个点具体是离哪个起点最近可以同步维护一个source_id数组在更新距离时记录起点的索引。2.3 实战案例腐烂的橘子LeetCode 994题“腐烂的橘子”是多源BFS的经典例题。网格中每个单元格可能有三种状态空单元格0、新鲜橘子1、腐烂橘子2。每分钟与腐烂橘子相邻的新鲜橘子都会腐烂。问直到没有新鲜橘子为止所必须经过的最小分钟数如果不可能则返回-1。解题思路初始化队列时遍历整个网格将所有腐烂橘子值为2的坐标加入队列并将这些点的“腐烂时间”设为0。同时统计新鲜橘子的数量。进行多源BFS。每从队列中取出一个腐烂橘子就检查其上下左右四个方向的新鲜橘子值为1将其腐烂值设为2时间设为当前时间1然后加入队列同时新鲜橘子计数减1。BFS结束后如果新鲜橘子计数为0返回最后腐烂的那个橘子的时间即BFS扩散的层数否则返回-1。这个例子完美展示了多源BFS如何将“多个同时发生的独立过程”统一到一个BFS框架中处理代码简洁且高效。3. 最小步数模型当“步长”不再均等标准BFS的每一“步”代价是相同的通常为1。但很多问题中不同的移动方式或状态转移消耗的“步数”或“代价”是不同的。例如走迷宫时向上向下走消耗1点体力而使用传送门消耗0点体力。这时如果我们仍用普通队列进行BFS就无法保证第一次扩展到某个节点时路径代价是最小的因为队列的FIFO性质只保证了“步数层数”的单调性无法保证“代价”的单调性。最小步数模型的核心是寻找从起点到终点的最小代价路径其中边的权值可能为0或其它正数。3.1 问题抽象与解决方案对比我们把问题抽象为图节点是状态边是状态转移边权是转移的代价。目标是求起点到终点的最短路。如果所有边权相等通常为1普通BFS队列完美解决时间复杂度O(NE)。如果边权只有两种例如0和1双端队列广搜0-1 BFS是更优解时间复杂度依然是O(NE)。如果边权为任意非负值需要使用优先队列Dijkstra算法时间复杂度O((NE) log N)。如果边权有负数需要使用Bellman-Ford或SPFA算法。本节重点讨论边权为0和1的情况即双端队列广搜它是解决最小步数模型的一把利器。3.2 双端队列广搜0-1 BFS原理为什么普通队列不行假设从节点A出发到节点B代价为0到节点C代价为1。A出队后将B和C入队。由于队列是FIFOB和C在队列中的顺序取决于入队顺序。如果C先入队那么C就会在B之前出队并被访问。但C的路径代价是1B的代价是0。从B出发可能扩展到更优的路径但因为C先出队可能导致某些节点被非最优的路径从C而来首次访问从而得到错误结果。双端队列deque广搜的智慧在于它根据扩展边的权值决定新节点加入队列的哪一端。如果扩展边的权值为0说明这是一条“免费”的边新节点的代价与当前节点相同。我们将新节点从队头加入。这样它会在当前层或代价相同的其他节点之后、代价更高的节点之前被处理。如果扩展边的权值为1说明这是一条“正常消耗”的边新节点的代价是当前节点代价1。我们将新节点从队尾加入就像普通BFS一样。这个操作保证了队列中的节点其代价始终是单调非递减的队头代价最小队尾代价最大。因此当一个节点第一次从队头被取出时它对应的代价就一定是最小代价。这个性质与优先队列Dijkstra类似但针对0-1权值的图使用双端队列的均摊时间复杂度是O(NE)比优先队列的O((NE) log N)更优。3.3 0-1 BFS模板与实例分析我们以一道经典问题为例在一个网格迷宫中可以上下左右移动代价为1同时地图上有些位置是“传送门”使用传送门可以瞬间到达另一个特定位置代价为0。求起点到终点的最小代价。from collections import deque def zero_one_bfs(grid, start, end, portals): :param grid: 网格0可走1障碍 :param start: 起点 (sx, sy) :param end: 终点 (ex, ey) :param portals: 传送门字典 key(x1,y1), value(x2,y2) :return: 最小代价 m, n len(grid), len(grid[0]) dist [[float(inf)] * n for _ in range(m)] dist[start[0]][start[1]] 0 dq deque() dq.append(start) while dq: x, y dq.popleft() current_cost dist[x][y] # 如果当前点就是终点可以提前返回因为队列单调第一次遇到即最小 if (x, y) end: return current_cost # 情况1使用传送门代价0 if (x, y) in portals: nx, ny portals[(x, y)] if dist[nx][ny] current_cost: # 发现更优路径 dist[nx][ny] current_cost dq.appendleft((nx, ny)) # 代价为0从队头入队 # 情况2向四个方向移动代价1 for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]: nx, ny x dx, y dy if 0 nx m and 0 ny n and grid[nx][ny] 0: if dist[nx][ny] current_cost 1: dist[nx][ny] current_cost 1 dq.append((nx, ny)) # 代价为1从队尾入队 return -1 # 无法到达关键点解析距离数组初始化使用float(inf)初始化方便比较更新。入队逻辑这是0-1 BFS的灵魂。appendleft用于代价0的转移append用于代价1的转移。出队检查由于队列的单调性当一个节点第一次出队时其dist值就是最终的最小代价。因此我们可以在出队时判断是否到达终点并直接返回。状态判重我们使用dist[nx][ny] new_cost进行判断和更新这同时完成了“访问检查”和“松弛操作”。一个节点可能会被多次更新和入队但只有带来更小代价的更新才会生效。避坑指南不要混淆“步数”和“代价”在普通BFS中dist记录的是步数层数。在0-1 BFS中dist记录的是累计算代价。队列的单调性是基于代价的。确保权值仅为0或1如果存在其他权值如20-1 BFS将失效必须使用优先队列。理解“入队多次”一个节点可能因为通过不同路径、以不同代价被多次发现并更新入队。这是正常的也是算法正确性的保证不同于普通BFS的“一次访问”。4. 双向广搜应对指数级增长的搜索空间当搜索空间非常庞大时例如状态数随步数指数级增长从起点开始的单向BFS可能会探索过多的节点导致时间或内存超限。双向广搜Bidirectional BFS是一种优化策略它同时从起点和终点开始进行BFS当两个搜索方向相遇时路径即被找到。4.1 为什么需要双向广搜考虑一个分支因子为b的图从起点到终点的最短路径长度为L。单向BFS需要探索的节点数量级约为 O(b^L)。而双向广搜从两头开始假设在中间点d处相遇那么起点端探索到深度d终点端探索到深度L-d。总探索节点数约为 O(b^d b^{L-d})。当d接近L/2时这个和远小于 O(b^L)。理论上在最理想情况下中点相遇它能将搜索空间从指数级开根号。4.2 算法流程与实现要点初始化两个队列q_start和q_end分别从起点和终点开始。初始化两个距离/访问字典visited_start和visited_end记录从各自起点出发到每个节点的距离同时用于判重。交替扩展在每一轮循环中选择当前节点数较少的方向进行一层扩展这有助于平衡两边的搜索进度。相遇判断在扩展一个节点时检查它是否出现在另一个方向的已访问集合中。如果出现则找到了一条连通路径。总路径长度 visited_start[current] visited_end[current] 1注意当前节点被两边各算了一次需要加1来连接。终止条件任一队列为空说明起点和终点不连通或找到相遇节点。from collections import deque def bidirectional_bfs(graph, start, end): :param graph: 邻接表表示的图 {node: [neighbor1, neighbor2...]} :param start: 起始节点 :param end: 目标节点 :return: 最短路径长度不可达返回-1 if start end: return 0 # 初始化两个方向的队列和访问字典 q_start deque([start]) q_end deque([end]) visited_start {start: 0} # 记录节点到起点的距离 visited_end {end: 0} # 记录节点到终点的距离 while q_start and q_end: # 选择较小的方向进行扩展优化搜索平衡 # 扩展起点方向 for _ in range(len(q_start)): node q_start.popleft() current_step visited_start[node] for neighbor in graph[node]: if neighbor not in visited_start: # 检查是否与终点方向相遇 if neighbor in visited_end: return current_step 1 visited_end[neighbor] visited_start[neighbor] current_step 1 q_start.append(neighbor) # 扩展终点方向 for _ in range(len(q_end)): node q_end.popleft() current_step visited_end[node] for neighbor in graph[node]: if neighbor not in visited_end: # 检查是否与起点方向相遇 if neighbor in visited_start: return visited_start[neighbor] 1 current_step visited_end[neighbor] current_step 1 q_end.append(neighbor) return -1实现细节与常见问题相遇点计算路径长度是dist_start[meet] dist_end[meet]。因为从起点到相遇点的距离是dist_start[meet]从相遇点到终点的距离是dist_end[meet]两者相加即为总长。注意有些实现中dist_end记录的是从终点出发的距离计算时直接相加即可。交替扩展与层扩展代码中使用了for _ in range(len(q))来确保每次扩展一层这保持了BFS的层序特性便于正确计算路径长度和判断相遇。选择扩展方向简单的策略是每次选择队列长度较小的方向进行扩展这有助于两边搜索均衡发展更快相遇。图的无向性双向BFS通常用于无向图或状态可逆的问题。如果是有向图需要确保从终点方向也是可搜索的即反向建图。状态表示对于复杂状态如二维坐标、字符串等需要确保哈希一致通常用元组或字符串作为字典的键。4.3 适用场景与局限性适用场景知道明确的起点和终点。状态空间巨大单向BFS会超时/超内存。状态转移是可逆的或者可以为终点方向构造反向的转移规则。局限性需要保存两个访问集合内存开销约为单向BFS的两倍。代码实现比单向BFS复杂。对于某些问题终点可能不唯一或难以定义则不适用。一个经典的应用场景是“单词接龙”问题LeetCode 127给定单词列表、起点词和终点词每次只能改变一个字母求最短转换序列长度。单词列表可以很长构成一个庞大的图使用双向BFS可以显著提速。5. 融会贯通复杂场景下的综合应用与调优在实际问题中这些技巧往往不是孤立的可能需要组合使用或者根据问题特点进行微调。5.1 组合使用案例想象这样一个问题在一个网格战场上有多个己方单位起点有多个敌方基地终点。地图上有平原移动消耗1、沼泽移动消耗2和己方建设的快速通道移动消耗0。求己方任一单位到达任一敌方基地的最小最大代价即最小化最远那个单位的代价。这个问题融合了多个模型多源多个己方单位作为起点。最小步数非0-1权值移动代价有0,1,2三种。多目标多个敌方基地作为终点。解决方案思路首先使用多源BFS的思想初始化将所有己方单位加入优先队列因为代价不全是1所以用优先队列实现Dijkstra距离设为0。然后运行Dijkstra算法因为边权有0,1,2计算网格上每个点到最近己方单位的距离。最后遍历所有敌方基地从上面计算出的距离数组中取值找到其中的最大值即为“最小最大代价”。这个例子展示了如何将多源思想与处理非均一权重的算法Dijkstra结合。5.2 性能调优与剪枝即使使用了高级技巧在极端情况下仍需考虑优化。双向广搜的启发式选择不一定总是交替扩展。可以根据问题的启发式信息优先扩展“看起来”更可能接近对方的方向。例如在网格寻路中可以优先扩展离对方直线距离更近的方向上的节点。状态压缩对于BFS的状态如果可以用一个整数而不是结构体或元组表示能极大提升访问判断和哈希的速度。例如将二维坐标(x, y)压缩为x * n y。提前终止在双向BFS中如果某一方向已经探索了非常深的层次但仍未相遇而另一方向只探索了很浅的层次可能意味着路径很长或不存在可以设置一个深度差阈值来提前终止。层级优化与A*搜索对于有明确坐标的问题双向BFS可以结合A*的启发函数来指导搜索方向进一步提升效率。但这已经超出了纯BFS的范畴进入了启发式搜索领域。5.3 调试与验证心得实现这些进阶BFS时调试是关键。以下是我常用的方法从小样例开始构造一个最小规模的、能体现算法特性的测试用例。例如测试0-1 BFS时构造一个必须使用0权边才能得到最优解的小图。可视化中间状态对于网格问题打印出每一步或每层后的距离数组或访问状态与手工推导的结果对比。这对于验证多源BFS的扩散顺序、0-1 BFS的队列状态非常有效。与朴素算法对比对于中等规模的问题可以用运行较慢但正确的算法如单向BFS求无权图Dijkstra求有权图作为基准验证你的优化算法如双向BFS0-1 BFS结果的正确性。关注边界条件起点终点相同、起点即障碍、空地图、只有一个点等边界情况最容易出错。理解算法失效的原因如果结果不对回归算法本质思考。例如双向BFS出错检查相遇点计算是否正确0-1 BFS出错检查是否误将权值大于1的边当成了0或1处理。掌握这些BFS的进阶技巧本质上是在理解图搜索算法核心思想的基础上针对具体问题约束多起点、非均一权重、巨大状态空间进行精准优化。它们不是死记硬背的模板而是一种思维模式如何将问题高效地映射到“状态”和“转移”上并选用合适的搜索策略来遍历这个状态空间。在实际编码中清晰的逻辑和对数据结构的熟练运用比生搬硬套模板更重要。先从理解每一个技巧背后的“为什么”开始然后通过大量练习形成肌肉记忆最终你就能在面对复杂搜索问题时快速识别特征并组合出高效的解决方案。
BFS进阶：多源、0-1权值与双向搜索实战解析
1. 从单源到多源BFS的思维跃迁在算法竞赛和日常开发中广度优先搜索BFS是解决图论、网格搜索问题的基石。我们最熟悉的场景是从一个起点出发逐层向外扩散直到找到目标或遍历全图。这就像一滴墨水滴入清水波纹一圈圈散开。但现实问题往往更复杂如果同时有多个起点呢如果每一步的“代价”不同呢如果地图太大单向搜索效率太低呢这就是BFS进阶技巧的用武之地。今天我们不谈BFS的基础模板直接切入四个能显著提升你解题能力和代码效率的进阶模型多源BFS、最小步数模型、双端队列广搜和双向广搜。它们不是孤立的技巧而是针对不同问题特征的精准工具。理解它们你就能在面对诸如“多个感染源同时扩散”、“不同移动方式消耗不同”、“地图巨大搜索超时”等问题时游刃有余。接下来我会结合具体场景和代码带你逐一拆解这些技巧的核心思想、实现细节以及那些容易踩坑的地方。2. 多源BFS当“起点”不止一个传统的BFS队列初始化时只放入一个起点。多源BFS的核心思想极其简单在初始化队列时将所有起点一次性全部加入队列并正确初始化它们的距离。这样BFS的扩散过程就会从所有这些起点“同时”开始仿佛它们是一个整体源。2.1 核心思想与适用场景为什么这么做是有效的因为BFS保证了两点一是队列的先进先出FIFO特性二是当第一次访问到一个节点时距离就是最短的。当我们把所有起点同时入队它们都处于“第0层”。接下来从队列中弹出的节点无论它来自哪个原始起点BFS都会保证我们是以最小的层数即最短距离访问到新的节点。最终对于图中任意一点其距离值就是离它最近的那个起点的距离。典型场景火灾蔓延/病毒传播地图上有多个火源病毒源求每个位置被点燃感染的最早时间。最近距离场计算在网格中有多个目标点如商店、医院求地图上每个格子离最近目标点的距离。这在游戏AI寻路、图像处理距离变换中非常有用。多起点最短路径问题本质是求所有点到一组起点的最近距离而不是到一个起点的距离。2.2 实现模板与关键细节实现上与单源BFS差异很小关键在于初始化。我们以经典的“01网格中多个起点的最短距离”为例。from collections import deque def multi_source_bfs(grid, sources): :param grid: 二维网格0表示可通行1表示障碍根据题意 :param sources: 起点列表每个元素为 (x, y) :return: dist二维数组记录每个点到最近起点的距离不可达为-1 m, n len(grid), len(grid[0]) dist [[-1] * n for _ in range(m)] # 初始化为-1表示未访问 q deque() # 关键步骤多源初始化 for sx, sy in sources: if grid[sx][sy] 0: # 起点本身需合法 dist[sx][sy] 0 q.append((sx, sy)) # 标准BFS过程 directions [(0,1), (0,-1), (1,0), (-1,0)] while q: x, y q.popleft() for dx, dy in directions: nx, ny x dx, y dy # 检查边界、障碍物、是否已访问 if 0 nx m and 0 ny n and grid[nx][ny] 0 and dist[nx][ny] -1: dist[nx][ny] dist[x][y] 1 q.append((nx, ny)) return dist关键细节与避坑点距离数组初始化dist数组通常初始化为一个特殊值如-1或无穷大用于判断是否访问过。起点的距离初始化为0。起点合法性检查并非所有传入的源点都一定合法例如可能是障碍物入队前需要判断。与单源BFS的代码复用你会发现除了初始化部分后面的BFS循环和单源完全一样。这体现了多源BFS只是初始状态的不同搜索过程本身没有变化。时间复杂度依然是O(N)其中N为网格节点数。因为每个节点依然只入队、出队一次。注意多源BFS得到的是每个点到“最近起点”的距离。如果你需要知道这个点具体是离哪个起点最近可以同步维护一个source_id数组在更新距离时记录起点的索引。2.3 实战案例腐烂的橘子LeetCode 994题“腐烂的橘子”是多源BFS的经典例题。网格中每个单元格可能有三种状态空单元格0、新鲜橘子1、腐烂橘子2。每分钟与腐烂橘子相邻的新鲜橘子都会腐烂。问直到没有新鲜橘子为止所必须经过的最小分钟数如果不可能则返回-1。解题思路初始化队列时遍历整个网格将所有腐烂橘子值为2的坐标加入队列并将这些点的“腐烂时间”设为0。同时统计新鲜橘子的数量。进行多源BFS。每从队列中取出一个腐烂橘子就检查其上下左右四个方向的新鲜橘子值为1将其腐烂值设为2时间设为当前时间1然后加入队列同时新鲜橘子计数减1。BFS结束后如果新鲜橘子计数为0返回最后腐烂的那个橘子的时间即BFS扩散的层数否则返回-1。这个例子完美展示了多源BFS如何将“多个同时发生的独立过程”统一到一个BFS框架中处理代码简洁且高效。3. 最小步数模型当“步长”不再均等标准BFS的每一“步”代价是相同的通常为1。但很多问题中不同的移动方式或状态转移消耗的“步数”或“代价”是不同的。例如走迷宫时向上向下走消耗1点体力而使用传送门消耗0点体力。这时如果我们仍用普通队列进行BFS就无法保证第一次扩展到某个节点时路径代价是最小的因为队列的FIFO性质只保证了“步数层数”的单调性无法保证“代价”的单调性。最小步数模型的核心是寻找从起点到终点的最小代价路径其中边的权值可能为0或其它正数。3.1 问题抽象与解决方案对比我们把问题抽象为图节点是状态边是状态转移边权是转移的代价。目标是求起点到终点的最短路。如果所有边权相等通常为1普通BFS队列完美解决时间复杂度O(NE)。如果边权只有两种例如0和1双端队列广搜0-1 BFS是更优解时间复杂度依然是O(NE)。如果边权为任意非负值需要使用优先队列Dijkstra算法时间复杂度O((NE) log N)。如果边权有负数需要使用Bellman-Ford或SPFA算法。本节重点讨论边权为0和1的情况即双端队列广搜它是解决最小步数模型的一把利器。3.2 双端队列广搜0-1 BFS原理为什么普通队列不行假设从节点A出发到节点B代价为0到节点C代价为1。A出队后将B和C入队。由于队列是FIFOB和C在队列中的顺序取决于入队顺序。如果C先入队那么C就会在B之前出队并被访问。但C的路径代价是1B的代价是0。从B出发可能扩展到更优的路径但因为C先出队可能导致某些节点被非最优的路径从C而来首次访问从而得到错误结果。双端队列deque广搜的智慧在于它根据扩展边的权值决定新节点加入队列的哪一端。如果扩展边的权值为0说明这是一条“免费”的边新节点的代价与当前节点相同。我们将新节点从队头加入。这样它会在当前层或代价相同的其他节点之后、代价更高的节点之前被处理。如果扩展边的权值为1说明这是一条“正常消耗”的边新节点的代价是当前节点代价1。我们将新节点从队尾加入就像普通BFS一样。这个操作保证了队列中的节点其代价始终是单调非递减的队头代价最小队尾代价最大。因此当一个节点第一次从队头被取出时它对应的代价就一定是最小代价。这个性质与优先队列Dijkstra类似但针对0-1权值的图使用双端队列的均摊时间复杂度是O(NE)比优先队列的O((NE) log N)更优。3.3 0-1 BFS模板与实例分析我们以一道经典问题为例在一个网格迷宫中可以上下左右移动代价为1同时地图上有些位置是“传送门”使用传送门可以瞬间到达另一个特定位置代价为0。求起点到终点的最小代价。from collections import deque def zero_one_bfs(grid, start, end, portals): :param grid: 网格0可走1障碍 :param start: 起点 (sx, sy) :param end: 终点 (ex, ey) :param portals: 传送门字典 key(x1,y1), value(x2,y2) :return: 最小代价 m, n len(grid), len(grid[0]) dist [[float(inf)] * n for _ in range(m)] dist[start[0]][start[1]] 0 dq deque() dq.append(start) while dq: x, y dq.popleft() current_cost dist[x][y] # 如果当前点就是终点可以提前返回因为队列单调第一次遇到即最小 if (x, y) end: return current_cost # 情况1使用传送门代价0 if (x, y) in portals: nx, ny portals[(x, y)] if dist[nx][ny] current_cost: # 发现更优路径 dist[nx][ny] current_cost dq.appendleft((nx, ny)) # 代价为0从队头入队 # 情况2向四个方向移动代价1 for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]: nx, ny x dx, y dy if 0 nx m and 0 ny n and grid[nx][ny] 0: if dist[nx][ny] current_cost 1: dist[nx][ny] current_cost 1 dq.append((nx, ny)) # 代价为1从队尾入队 return -1 # 无法到达关键点解析距离数组初始化使用float(inf)初始化方便比较更新。入队逻辑这是0-1 BFS的灵魂。appendleft用于代价0的转移append用于代价1的转移。出队检查由于队列的单调性当一个节点第一次出队时其dist值就是最终的最小代价。因此我们可以在出队时判断是否到达终点并直接返回。状态判重我们使用dist[nx][ny] new_cost进行判断和更新这同时完成了“访问检查”和“松弛操作”。一个节点可能会被多次更新和入队但只有带来更小代价的更新才会生效。避坑指南不要混淆“步数”和“代价”在普通BFS中dist记录的是步数层数。在0-1 BFS中dist记录的是累计算代价。队列的单调性是基于代价的。确保权值仅为0或1如果存在其他权值如20-1 BFS将失效必须使用优先队列。理解“入队多次”一个节点可能因为通过不同路径、以不同代价被多次发现并更新入队。这是正常的也是算法正确性的保证不同于普通BFS的“一次访问”。4. 双向广搜应对指数级增长的搜索空间当搜索空间非常庞大时例如状态数随步数指数级增长从起点开始的单向BFS可能会探索过多的节点导致时间或内存超限。双向广搜Bidirectional BFS是一种优化策略它同时从起点和终点开始进行BFS当两个搜索方向相遇时路径即被找到。4.1 为什么需要双向广搜考虑一个分支因子为b的图从起点到终点的最短路径长度为L。单向BFS需要探索的节点数量级约为 O(b^L)。而双向广搜从两头开始假设在中间点d处相遇那么起点端探索到深度d终点端探索到深度L-d。总探索节点数约为 O(b^d b^{L-d})。当d接近L/2时这个和远小于 O(b^L)。理论上在最理想情况下中点相遇它能将搜索空间从指数级开根号。4.2 算法流程与实现要点初始化两个队列q_start和q_end分别从起点和终点开始。初始化两个距离/访问字典visited_start和visited_end记录从各自起点出发到每个节点的距离同时用于判重。交替扩展在每一轮循环中选择当前节点数较少的方向进行一层扩展这有助于平衡两边的搜索进度。相遇判断在扩展一个节点时检查它是否出现在另一个方向的已访问集合中。如果出现则找到了一条连通路径。总路径长度 visited_start[current] visited_end[current] 1注意当前节点被两边各算了一次需要加1来连接。终止条件任一队列为空说明起点和终点不连通或找到相遇节点。from collections import deque def bidirectional_bfs(graph, start, end): :param graph: 邻接表表示的图 {node: [neighbor1, neighbor2...]} :param start: 起始节点 :param end: 目标节点 :return: 最短路径长度不可达返回-1 if start end: return 0 # 初始化两个方向的队列和访问字典 q_start deque([start]) q_end deque([end]) visited_start {start: 0} # 记录节点到起点的距离 visited_end {end: 0} # 记录节点到终点的距离 while q_start and q_end: # 选择较小的方向进行扩展优化搜索平衡 # 扩展起点方向 for _ in range(len(q_start)): node q_start.popleft() current_step visited_start[node] for neighbor in graph[node]: if neighbor not in visited_start: # 检查是否与终点方向相遇 if neighbor in visited_end: return current_step 1 visited_end[neighbor] visited_start[neighbor] current_step 1 q_start.append(neighbor) # 扩展终点方向 for _ in range(len(q_end)): node q_end.popleft() current_step visited_end[node] for neighbor in graph[node]: if neighbor not in visited_end: # 检查是否与起点方向相遇 if neighbor in visited_start: return visited_start[neighbor] 1 current_step visited_end[neighbor] current_step 1 q_end.append(neighbor) return -1实现细节与常见问题相遇点计算路径长度是dist_start[meet] dist_end[meet]。因为从起点到相遇点的距离是dist_start[meet]从相遇点到终点的距离是dist_end[meet]两者相加即为总长。注意有些实现中dist_end记录的是从终点出发的距离计算时直接相加即可。交替扩展与层扩展代码中使用了for _ in range(len(q))来确保每次扩展一层这保持了BFS的层序特性便于正确计算路径长度和判断相遇。选择扩展方向简单的策略是每次选择队列长度较小的方向进行扩展这有助于两边搜索均衡发展更快相遇。图的无向性双向BFS通常用于无向图或状态可逆的问题。如果是有向图需要确保从终点方向也是可搜索的即反向建图。状态表示对于复杂状态如二维坐标、字符串等需要确保哈希一致通常用元组或字符串作为字典的键。4.3 适用场景与局限性适用场景知道明确的起点和终点。状态空间巨大单向BFS会超时/超内存。状态转移是可逆的或者可以为终点方向构造反向的转移规则。局限性需要保存两个访问集合内存开销约为单向BFS的两倍。代码实现比单向BFS复杂。对于某些问题终点可能不唯一或难以定义则不适用。一个经典的应用场景是“单词接龙”问题LeetCode 127给定单词列表、起点词和终点词每次只能改变一个字母求最短转换序列长度。单词列表可以很长构成一个庞大的图使用双向BFS可以显著提速。5. 融会贯通复杂场景下的综合应用与调优在实际问题中这些技巧往往不是孤立的可能需要组合使用或者根据问题特点进行微调。5.1 组合使用案例想象这样一个问题在一个网格战场上有多个己方单位起点有多个敌方基地终点。地图上有平原移动消耗1、沼泽移动消耗2和己方建设的快速通道移动消耗0。求己方任一单位到达任一敌方基地的最小最大代价即最小化最远那个单位的代价。这个问题融合了多个模型多源多个己方单位作为起点。最小步数非0-1权值移动代价有0,1,2三种。多目标多个敌方基地作为终点。解决方案思路首先使用多源BFS的思想初始化将所有己方单位加入优先队列因为代价不全是1所以用优先队列实现Dijkstra距离设为0。然后运行Dijkstra算法因为边权有0,1,2计算网格上每个点到最近己方单位的距离。最后遍历所有敌方基地从上面计算出的距离数组中取值找到其中的最大值即为“最小最大代价”。这个例子展示了如何将多源思想与处理非均一权重的算法Dijkstra结合。5.2 性能调优与剪枝即使使用了高级技巧在极端情况下仍需考虑优化。双向广搜的启发式选择不一定总是交替扩展。可以根据问题的启发式信息优先扩展“看起来”更可能接近对方的方向。例如在网格寻路中可以优先扩展离对方直线距离更近的方向上的节点。状态压缩对于BFS的状态如果可以用一个整数而不是结构体或元组表示能极大提升访问判断和哈希的速度。例如将二维坐标(x, y)压缩为x * n y。提前终止在双向BFS中如果某一方向已经探索了非常深的层次但仍未相遇而另一方向只探索了很浅的层次可能意味着路径很长或不存在可以设置一个深度差阈值来提前终止。层级优化与A*搜索对于有明确坐标的问题双向BFS可以结合A*的启发函数来指导搜索方向进一步提升效率。但这已经超出了纯BFS的范畴进入了启发式搜索领域。5.3 调试与验证心得实现这些进阶BFS时调试是关键。以下是我常用的方法从小样例开始构造一个最小规模的、能体现算法特性的测试用例。例如测试0-1 BFS时构造一个必须使用0权边才能得到最优解的小图。可视化中间状态对于网格问题打印出每一步或每层后的距离数组或访问状态与手工推导的结果对比。这对于验证多源BFS的扩散顺序、0-1 BFS的队列状态非常有效。与朴素算法对比对于中等规模的问题可以用运行较慢但正确的算法如单向BFS求无权图Dijkstra求有权图作为基准验证你的优化算法如双向BFS0-1 BFS结果的正确性。关注边界条件起点终点相同、起点即障碍、空地图、只有一个点等边界情况最容易出错。理解算法失效的原因如果结果不对回归算法本质思考。例如双向BFS出错检查相遇点计算是否正确0-1 BFS出错检查是否误将权值大于1的边当成了0或1处理。掌握这些BFS的进阶技巧本质上是在理解图搜索算法核心思想的基础上针对具体问题约束多起点、非均一权重、巨大状态空间进行精准优化。它们不是死记硬背的模板而是一种思维模式如何将问题高效地映射到“状态”和“转移”上并选用合适的搜索策略来遍历这个状态空间。在实际编码中清晰的逻辑和对数据结构的熟练运用比生搬硬套模板更重要。先从理解每一个技巧背后的“为什么”开始然后通过大量练习形成肌肉记忆最终你就能在面对复杂搜索问题时快速识别特征并组合出高效的解决方案。