双向 BFSCSP-S

💡 核心思想

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

🎯 直觉理解

想象你在找两个朋友之间的最短路径。普通 BFS 是你从朋友 A 出发，向四周扩散找人 B。双向 BFS 则是 A 和 B 同时向中间走，相遇时路径一定最短。就像两个人在黑暗中互相寻找，每人举着一个手电筒，当光束相遇时就找到了对方。

📝 算法流程

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;
}

⚠️ 常见坑点

📚 相关题目