2 - 双向BFS

思想

在之前的BFS习题中，有一类 知道搜索起点和终点的BFS（如八数码，开锁等） 值得注意。可以用双向BFS的方法提高一点效率。

双向BFS：从起点和中点同时开始BFS，当两边有交集时结束。

如何使用

代码框架如下：

// 这里用集合不用队列, 以快速判断两边是否有交集
set q1, q2;

// BFS
q1.insert(起点);
q2.insert(终点);

while (q1不空 && q2不空)
{
    // 选择较小集合进行扩充
    q1 = q1, q2中元素个数较小的;
    q2 = q1, q2中元素个数较大的;
    
    取队头t
    扩散队头t
}

练习题

打开转盘锁

752. 打开转盘锁 - 力扣（LeetCode）

使用双向BFS改进后的代码如下：

int openLock(vector<string>& deadends, string target) {
    // 使用Hash存储deadends, 进行O(1)查询节省时间
    unordered_set<string> visited;
    visited.insert(deadends.begin(), deadends.end());

    // 直接得出答案的情况
    if (visited.count(target))  return -1;
    if (target == "0000")    return 0;

    // BFS
    map<string, int> q1, q2;
    q1["0000"] = 0;
    q2[target] = 0;
    while (!q1.empty() && !q2.empty())
    {
        // 取较小集合
        if (q1.size() > q2.size())
            q1.swap(q2);

        // 取队头
        map<string, int> tempQ;
        for (auto [cur, ans] : q1)
        {
            // 验证是否是答案
            if (q2.contains(cur))
                return ans + q2[cur];
            // 转到deadend里的数字就放弃BFS
            if (visited.count(cur))
                continue;

            // 拓展队头(扩充结果存在tempQ里, 否则q1会无限扩充)
            visited.insert(cur);
            for (int i = 0; i < 4; ++i)
            {
                string tmp = plus(cur, i);
                if (!visited.count(tmp))
                    tempQ[tmp] = ans + 1;

                tmp = minus(cur, i);
                if (!visited.count(tmp))
                    tempQ[tmp] = ans + 1;
            }
        }

        // 交替拓展节点
        q1 = q2;
        q2 = tempQ;
    }

    return -1;
}

参考资料

• 《labuladong的算法笔记》
• 算法基础课 - AcWing