双向 BFS

01 / 一句话本质

从两端同时跑 BFS。两侧边界一旦相遇,最短路即得。 优势随深度指数级增长:O(b^d) 变为 O(b^(d/2)) —— 只要源点与目标点都已知,就有效。
题目无权图上源到目标的最短路径长度输入graph=mesh, A → F
AS:0BCDEFT:0
从 A(正向)和 F(反向)同时跑 BFS。初始化 distS[A] = 0、distT[F] = 0,两边的边界各只有一个种子。
步
0 / 19
边界 |S|、|T|
1, 1
已访问
1 + 1
路径长度
—
0 / 19

02 / 模式骨架

# 层层推进的双向 BFSdistS ← { s: 0 }; distT ← { t: 0 }frontS ← {s}; frontT ← {t}while frontS 与 frontT 均非空:if |frontS| ≤ |frontT|: 用 frontS 探查 distTelse: 用 frontT 探查 distSfor u in front for v in adj[u]:if v 已在对侧: return same[u] + other[v] + 1if v 不在同侧: same[v] = same[u] + 1; nextFront ← vreturn −1 # 不连通

03 / 什么时候用这个模式

"最短变换 / 突变"
单词接龙、基因突变、转盘锁 —— 任何起点和终点都是具体状态、且边等代价(每跳一步)的状态空间搜索。
"两端都已知"
只有目标点是具体状态时才有用。 对一对多最短路(Dijkstra、源点 BFS),单侧 BFS 已足够,渐近同阶。
"分支因子大得让 BFS 吃不消"
单词接龙 26 字母 × L 位置,4 轮转盘锁 10 数字 —— 分支因子 b 看起来很吓人。双向 BFS 把深度减半,b^(d/2) 就可接受了。
"无权图最短路"
无权图 BFS 已最短;双向只加额外价值。带权图请用双向 Dijkstra(更高级,面试少考)。

04 / 常见坑

先扩展更大的那一侧。
关键就是让两侧边界平衡 —— 始终先展开较小的。 若一直展开"先到的那侧",一边会爆,加速消失。
更新之后才查对侧、而不是更新之前。
"相遇"检查每次探查邻居时都做 —— 在加入自己访问集合之前就看对侧。 否则可能错过第一次相遇,报出比真正最短更长的路径。
答案公式写反。
在 u → v 上相遇(u 在当前侧,v 已在对侧), 答案是 distSide[u] + distOther[v] + 1 ——+1 是中间这条桥。Off-by-one 是最经典的 bug。
把第一次相遇当成最短。
展开同一层时,可能有多个相遇候选出现 —— 若关心路径还原,处理完整层再下结论; 否则当前 BFS 不变量保证"该深度第一次相遇"即最短。

05 / 去 LeetCode 上练习

中等10

01Minimum Genetic Mutation— LC 433→0201 Matrix— LC 542→03Open the Lock— LC 752→04Rotting Oranges— LC 994→05Shortest Path in Binary Matrix— LC 1091→06As Far from Land as Possible— LC 1162→07Jump Game III— LC 1306→08Get Watched Videos by Your Friends— LC 1311→09Minimum Jumps to Reach Home— LC 1654→10Shortest Path to Get Food— LC 1730→

困难9

01Word Ladder II— LC 126→02Word Ladder— LC 127→03Cut Off Trees for Golf Event— LC 675→04Sliding Puzzle— LC 773→05Bus Routes— LC 815→06K-Similar Strings— LC 854→07Shortest Path to Get All Keys— LC 864→08Minimum Number of Flips to Convert Binary Matrix to Zero Matrix— LC 1284→09Shortest Path in a Grid with Obstacles Elimination— LC 1293→