双向 BFSNOIP

💡 核心思想

双向 BFS 是从起点和终点同时开始 BFS，当两个搜索前沿相遇时即找到最短路径。由于搜索树的分支因子为 b，深度为 d 时节点数为 O(b^d)，而双向 BFS 每侧只需搜索到 d/2，总节点数为 O(b^{d/2})，效率大幅提升。

🎯 直觉理解

双向 BFS 是"两头同时挖隧道"：从起点和终点各做一次 BFS，当两个搜索的前沿相遇时，路径就找到了。双向扩展开销是 $O(2 imes b^{d/2})$，而单向要 $b^d$——深度减半，时间天差地别。

比如八数码：单向搜 20 层可能上亿状态，双向各搜 10 层再相遇，状态数骤减。

前提是终点状态已知（像八数码那样目标明确），否则没法从终点反向扩展。实现上两个队列交替扩展，每扩展一层就检查对方访问过哪些状态。

📝 算法流程

1. 初始化两个队列：q1（从起点搜索）、q2（从终点搜索）
2. 初始化两个 visited 集合
3. 每次扩展时，选择当前节点数较少的一侧进行扩展
4. 对于每个扩展出的新状态，检查是否在另一侧的 visited 中
5. 如果相遇，返回当前步数之和
6. 如果某队列为空，说明无解

$$\text{节点数：}O(b^{d/2}) \ll O(b^d)\text{（普通 BFS）}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;

// 双向 BFS 模板（以字符串变换为例）
int bidirectionalBFS(string start, string target, 
                     function(string)> expand) {
    if (start == target) return 0;
    
    unordered_set vis1, vis2;
    queue> q1, q2;
    q1.push({start, 0}); vis1.insert(start);
    q2.push({target, 0}); vis2.insert(target);
    
    while (!q1.empty() && !q2.empty()) {
        // 每次扩展较小的一侧
        auto& q = (q1.size() <= q2.size()) ? q1 : q2;
        auto& vis = (q1.size() <= q2.size()) ? vis1 : vis2;
        auto& otherVis = (q1.size() <= q2.size()) ? vis2 : vis1;
        
        int sz = q.size();
        while (sz--) {
            auto [cur, d] = q.front(); q.pop();
            for (auto& nxt : expand(cur)) {
                if (otherVis.count(nxt)) return d + 1 + /*另一侧深度*/ 0;
                if (!vis.count(nxt)) {
                    vis.insert(nxt);
                    q.push({nxt, d + 1});
                }
            }
        }
    }
    return -1; // 无解
}

int main() {
    // 示例：从 "0000" 到 "1234"，每次变换一位
    // 实际题目需要提供 expand 函数
    return 0;
}

⚠️ 常见坑点

📚 相关题目