2 - 双向BFS
思想
在之前的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