双向BFS：从两头同时搜索，更快找到最短路径

这是什么，用来干什么？

想象一下，你和小伙伴分别站在山洞的两端，同时向中间挖洞。你们各自挖自己的那一半，当两人在某处碰头时，整条隧道就通了。相比一个人从一端挖到另一端，两个人一起挖能省下一半左右的时间。这就是双向广度优先搜索（Bidirectional BFS）的核心思想——同时从起点和终点开始搜索，当两个方向的搜索相遇时，就找到了最短路径。

双向BFS特别适合处理“状态空间很大，但起点和终点都明确知道”的问题，比如走迷宫、八数码谜题、单词变换等。它可以把搜索空间从原来的 $O(b^d)$ 大幅降低到 $O(b^{d/2})$ （b是分支因子，d是距离），让程序跑得更快。

为什么双向BFS比单向BFS更快？

普通BFS像在水面丢一颗石子，波纹一圈一圈向外扩散。如果目标在很远的对岸，需要扩散几十圈才能碰到目标。这意味着要访问成千上万个状态。

双向BFS则像同时丢了两颗石子——一颗在起点，一颗在终点。两颗石子产生的波纹向中间扩散，当它们相遇时，中间的路径就找到了。由于每个方向只需要扩散到一半的距离，总访问的状态数大大减少。

举个生活中的例子：学校要组织一次从图书馆（起点）到体育馆（终点）的接力赛，整个校园很大，有无数条路。如果只有一个人从图书馆出发去找体育馆，他可能要跑遍整个校园。但如果让两个同时出发，一个从图书馆向体育馆方向跑，另一个从体育馆向图书馆方向跑，他们很快就能在中途碰头，接力完成。这就是双向搜索的力量。

关键实现细节

1. 两个队列 + 两个距离数组

用 queue 分别存储从起点出发和从终点出发的当前层节点。
用两个二维数组（或哈希表）记录每个节点是从哪边访问到的，以及到达该节点所用的步数。
初始化：起点入队1，距离设为0；终点入队2，距离设为0。

2. 判断“碰头”

当扩展一个节点时，检查它的邻居是否已经被另一个方向访问过。如果某个节点在另一个方向的距离数组中不为 -1（即已被访问），说明两个方向的搜索相遇了。此时最短路径长度 = 当前方向到达该节点的步数 + 另一个方向到达该节点的步数。

3. 平衡策略：每次扩展节点较少的那个方向

为了保持两个方向搜索进度大致相当，每次循环时，我们选择当前队列中节点数量较少的方向进行扩展。这样可以防止一个方向扩展得太多，另一个方向跟不上，从而保持整体搜索效率。

4. 距离计算

每个方向走到相遇点的步数相加，就是起点到终点的最短路径长度。

生活中的例子：迷宫寻宝

假设你参加一个迷宫寻宝游戏，迷宫是一个5×5的网格，0表示路，1表示墙。起点在左上角 (0,0)，宝藏藏在右下角 (4,4)。普通BFS需要一层层向外扩散，可能访问几十个格子。而双向BFS同时从起点和终点出发，它们很快就在迷宫中间相遇，只需访问一半左右的格子就能找到路径。

举个例子，下面这个迷宫（0是路，1是墙）：

起点(0,0)和终点(4,4)同时开始BFS，大约走到第2步时就会在某个格子碰头，总共只扩展了十来个节点，而单向BFS可能要扩展二十多个。

常见错误（新手容易踩的坑）

忘了特判起点等于终点
如果起点和终点是同一个格子，最短路径长度为0。不特判的话，程序会当成没找到路径或进入死循环。一定要在开头判断并直接返回0。
碰头检测顺序不对
扩展一个节点时，应该先更新当前方向的距离，然后再检查这个新节点是否已被另一个方向访问过。如果先检查再更新，可能会漏掉碰头的情况。
平衡策略反着写
错误地认为应该扩展节点多的方向（以为这个方向信息多），结果导致一个方向拼命扩展，另一个方向停滞不前，失去了双向搜索的意义。
忘记考虑边界和墙
扩展邻居时，必须检查坐标是否越界，以及该格子是否为墙（或障碍物）。否则可能把非法位置当成路径。
队列无限循环
如果问题本身无解（起点和终点不连通），双向BFS最终会清空两个队列。这时需要设定一个终止条件，比如当两个队列都为空时输出“无解”，否则程序会死循环。
把距离数组初始值设为0
距离数组通常初始化为 -1 表示未访问。如果用0表示未访问，那么起点距离为0会与未访问混淆，导致无法正确判断。

完整可运行的示例代码

下面是一个在5×5网格迷宫中用双向BFS找最短路径的完整程序。代码中有详细的中文注释，你可以直接复制运行。

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

// 四个方向：上、下、左、右
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int main() {
    int n = 5;
    vector<string> maze = {
        "00010",   // 第0行: 0 0 0 1 0
        "00100",   // 第1行: 0 0 1 0 0
        "01001",   // 第2行: 0 1 0 0 1
        "00000",   // 第3行: 0 0 0 0 0
        "00100"    // 第4行: 0 0 1 0 0
    };
    
    int sx = 0, sy = 0;            // 起点坐标 (0,0)
    int tx = 4, ty = 4;            // 终点坐标 (4,4)
    
    // 特判：起点就是终点
    if (sx == tx && sy == ty) {
        cout << 0 << endl;
        return 0;
    }
    
    // dist1: 从起点出发到达每个格子的步数，-1表示未访问
    vector<vector<int>> dist1(n, vector<int>(n, -1));
    // dist2: 从终点出发到达每个格子的步数
    vector<vector<int>> dist2(n, vector<int>(n, -1));
    
    queue<pair<int, int>> q1;   // 起点队列
    queue<pair<int, int>> q2;   // 终点队列
    
    q1.push({sx, sy});          // 起点入队
    dist1[sx][sy] = 0;          // 起点步数为0
    
    q2.push({tx, ty});          // 终点入队
    dist2[tx][ty] = 0;          // 终点步数为0
    
    // 扩展函数：从队列q中取出一个节点，扩展它的四个邻居
    auto expand = [&](queue<pair<int, int>>& q,
                      vector<vector<int>>& d1,
                      vector<vector<int>>& d2) -> int {
        int x = q.front().first, y = q.front().second;  // 取出当前格子坐标
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];       // 邻居的行
            int ny = y + dy[i];       // 邻居的列
            
            // 如果越界或者是墙，跳过
            if (nx < 0 || nx >= n || ny < 0 || ny >= n || maze[nx][ny] == '1')
                continue;
            
            // 如果这个方向已经访问过这个邻居，跳过
            if (d1[nx][ny] != -1)
                continue;
            
            // 更新当前方向到达邻居的步数
            d1[nx][ny] = d1[x][y] + 1;
            
            // 检查对面的队列是否已经访问过这个邻居
            if (d2[nx][ny] != -1) {
                // 两边碰头！距离 = 当前方向步数 + 对面方向步数
                return d1[nx][ny] + d2[nx][ny];
            }
            
            q.push({nx, ny});   // 新节点入队
        }
        return -1;  // 本次扩展没找到碰头点
    };
    
    int ans = -1;
    while (!q1.empty() && !q2.empty()) {
        // 平衡策略：每次扩展节点数较少的那个队列
        if (q1.size() <= q2.size()) {
            ans = expand(q1, dist1, dist2);
        } else {
            ans = expand(q2, dist2, dist1);
        }
        if (ans != -1) break;   // 找到路径，退出
    }
    
    if (ans != -1)
        cout << "最短路径长度 = " << ans << endl;
    else
        cout << "不存在路径" << endl;
    
    return 0;
}

运行结果：

最短路径长度 = 8

（在这个迷宫例子中，从(0,0)到(4,4)的最短路径需要走8步，你可以在纸上验证一下。）

总结与相关知识点

双向BFS是解决“已知起点和终点的最短路径问题”的高效算法，它通过双方向同时搜索，将搜索空间从 $O(b^d)$ 降低到 $O(b^{d/2})$ ，非常适合状态空间巨大的情况。

如果你想进一步探索，可以学习以下相关知识点：

单向BFS：双向BFS的基础，一定要先掌握好普通BFS的实现。
双向Dijkstra：如果路径上的边带有权值（不是每步长度都为1），可以用双向Dijkstra（即双向BFS的加权版本）。
A*搜索：如果还能估算当前节点到终点的距离（启发式函数），A*算法往往更快，但它需要设计好的启发函数。
*迭代加深搜索（IDA）**：结合深度优先搜索和启发式，适合内存有限的情况。

双向BFS是很多竞赛题的常客，比如八数码 Puzzle、单词接龙、迷宫最短路径等。掌握了它，你就能在搜索类问题中快人一步！

双向BFS——两个方向同时搜索更快