起点和终点都已知时，与其让一条水波独自扩散到终点，不如让两端同时扩散，在中间碰头——能省下大量不必要的搜索。
14.1 节的 BFS 已经能保证找到最短路，但它有一个隐藏的代价：如果图的分支因子（平均每个节点能扩展到多少个新节点）是 b，最短路长度是 d，那么单向 BFS 在最坏情况下要访问的节点数量级是 O(b^d)——随着 d 增大，访问的节点数会指数级爆炸。
如果终点也是已知的（比如"从状态 A 变到状态 B，最少几步"，A 和 B 都给定），有一个更聪明的办法：从起点和终点同时开始扩展，两边各自只需要扩展到大约 d/2 层，就能在中间相遇。这样访问的节点数量级变成 O(2 × b^(d/2))——同样是指数级，但指数减半带来的差距非常悬殊：
| 分支因子 b | 最短路 d | 单向 BFS 访问量 O(b^d) | 双向 BFS 访问量 O(2×b^(d/2)) |
|---|---|---|---|
| 10 | 6 | 约 1,000,000 | 约 2,000 |
| 10 | 10 | 约 100 亿 | 约 200,000 |
b^d 和 2×b^(d/2) 看起来只是指数少了一半，但因为是指数关系，一半的指数意味着底数相同时数值差了一个数量级以上的平方根倍。d 越大、b 越大，双向 BFS 相对单向 BFS 省下的计算量就越夸张。双向 BFS 维护两个独立的 BFS：一个从起点 S 出发向外扩展，一个从终点 T 出发向外扩展。两边各自维护自己的距离数组（distS、distT），交替扩展一层。每次扩展新节点时，检查这个节点有没有被另一边访问过——一旦发现某个节点同时被两边访问到，说明两股"水波"在这里相遇了，答案就是 distS[相遇点] + distT[相遇点]。
B 同时被"从 S 出发"和"从 T 出发"的两股搜索访问到：distS[B]=2，distT[B]=2，答案 = distS[B] + distT[B] = 4，和单向 BFS 算出的路径长度一致，但双向 BFS 全程只碰到了 S、A、B、C、T 中的每一个节点各一次，在真实的大规模图上（分支因子较大时）能少访问大量根本没必要看的节点。以一般图（邻接表）为例，两个方向交替各扩展一整层，每扩展一个新节点就检查它是否已经被对面访问过：
| 1 | vector<int> adj[MAXN]; |
| 2 | int distS[MAXN], distT[MAXN]; // -1 表示未访问；分别记录"从起点/终点出发"的距离 |
| 3 | |
| 4 | // 扩展 q 队列一整层；hitDist 是"对面"的距离数组，用来检测相遇 |
| 5 | int ExpandLayer(queue<int> &q, int myDist[], int hitDist[]) |
| 6 | { |
| 7 | int sz = q.size(); // 只扩展"当前已经在队列里"的这一层，不把新加入的也算进去 |
| 8 | for (int t = 0; t < sz; t++) |
| 9 | { |
| 10 | int u = q.front(); q.pop(); |
| 11 | for (int v : adj[u]) |
| 12 | { |
| 13 | if (hitDist[v] != -1) return myDist[u] + 1 + hitDist[v]; // ★ 对面已经到过 v，相遇！ |
| 14 | if (myDist[v] != -1) continue; // 自己这边已经访问过，跳过 |
| 15 | myDist[v] = myDist[u] + 1; |
| 16 | q.push(v); |
| 17 | } |
| 18 | } |
| 19 | return -1; // 这一层扩展完还没相遇 |
| 20 | } |
| 21 | |
| 22 | int BidirectionalBFS(int S, int T) |
| 23 | { |
| 24 | if (S == T) return 0; |
| 25 | memset(distS, -1, sizeof(distS)); |
| 26 | memset(distT, -1, sizeof(distT)); |
| 27 | queue<int> qS, qT; |
| 28 | distS[S] = 0; qS.push(S); |
| 29 | distT[T] = 0; qT.push(T); |
| 30 | |
| 31 | while (!qS.empty() && !qT.empty()) |
| 32 | { |
| 33 | int res = ExpandLayer(qS, distS, distT); // 从起点这边扩展一层 |
| 34 | if (res != -1) return res; |
| 35 | res = ExpandLayer(qT, distT, distS); // 从终点这边扩展一层 |
| 36 | if (res != -1) return res; |
| 37 | } |
| 38 | return -1; // 两边都扩展完了还没相遇，说明 S、T 不连通 |
| 39 | } |
q.size() 提前记录本层节点数，确保每次只扩展"已经在队列里"的这一层，不会把这一层扩展时新塞进去的下一层节点也算进当前这一轮——这样才能保证两边真正是"交替地一层一层"扩展，而不是一边偷跑到很深的地方。用一张网格图演示：起点 S 在左上角，终点 T 在右下角，两支队列交替扩展，直到某一层扩展时踩到对方的地盘：
distT[M] != -1（终点那边第 1 层已经到过 M）——相遇！直接返回 distS[M] + 1 + distT[M]双向 BFS 不是任何时候都能用，也不是任何时候都比单向 BFS 划算：
T 出发反向扩展时，要沿着反向边走（"谁能到达 T"而不是"T 能到达谁"），需要额外建一张反图。本节的例子和模板代码都以无向图为例，实际做有向图的双向 BFS 时要特别注意这一点。