双向 BFS

概念讲解

什么是双向 BFS？

从起点和终点同时 BFS，当两个搜索相遇时找到最短路径。

优势

将搜索空间从 O(bd)O(b^d) 降低到 O(bd/2)O(b^{d/2})。

实现

123456789101112131415161718int bidirectionalBFS(int start, int end) {
    queue<int> q1, q2;
    unordered_map<int,int> dist1, dist2;
    
    q1.push(start); dist1[start] = 0;
    q2.push(end); dist2[end] = 0;
    
    while (!q1.empty() && !q2.empty()) {
        // 从起点扩展
        int result = expand(q1, dist1, dist2);
        if (result != -1) return result;
        
        // 从终点扩展
        result = expand(q2, dist2, dist1);
        if (result != -1) return result;
    }
    return -1;
}

考点分析

初赛考查方式

  1. 程序阅读： 双向 BFS
  2. 编程题： 最短路径

常见考点

  • 双向 BFS 原理
  • 相遇判定
  • 效率分析

练习题

  1. 双向 BFS 的优势？
查看答案

双向 BFS 的优势：

将搜索空间从 O(bd)O(b^d) 降低到 O(bd/2)O(b^{d/2})。

其中 b 是分支因子，d 是搜索深度。

例如：b=10, d=6

  • 普通 BFS：106=100000010^6 = 1000000
  • 双向 BFS：2×103=20002 \times 10^3 = 2000
  1. 什么时候用双向 BFS？
查看答案

双向 BFS 适用于：

  1. 知道起点和终点
  2. 搜索空间很大
  3. 分支因子较大

例如：八数码问题、单词接龙等。

  1. 如何判断相遇？
查看答案

判断相遇的方法：

在扩展一个方向时，检查当前节点是否已被另一个方向访问过。

12345678910111213141516int expand(queue<int>& q, unordered_map<int,int>& dist1, unordered_map<int,int>& dist2) {
    int u = q.front();
    q.pop();
    
    for (int v : getNeighbors(u)) {
        if (dist2.count(v)) {
            return dist1[u] + 1 + dist2[v];
        }
        if (!dist1.count(v)) {
            dist1[v] = dist1[u] + 1;
            q.push(v);
        }
    }
    
    return -1;
}

易错点

⚠️ 注意：

  1. 要同时扩展两端
  2. 遇到已访问节点即相遇
  3. 适用于知道终点的情况
  4. 效率提升明显