BFS（广度优先搜索）优化技巧 — 双向遍历

BFS优化技巧 — 双向遍历

在之前我发过 动态规划框架 与 动态规划的优化技巧 — 空间压缩，类似的，BFS框架 也有相应的优化技巧 双向遍历。从技巧的名字就可以看出，双向遍历指的就是从起点开始找终点的同时，也从终点开始找起点，一旦两个寻找过程出现交集，那么起点到终点的路径也就找出来了。

严谨一点表示：传统的 BFS 框架就是从起点开始向四周扩散，遇到终点时停止；而双向 BFS 则是从起点和终点同时开始扩散，当两边有交集的时候停止。

同时扩散的话，效率肯定会更快一点，看下面两张图就会很明白了：

图的树形结构，【target】在最底层，按照传统BFS的遍历方式，需要从【start】开始，遍历所有节点，才能在最底层找到【target】，而双向遍历遍历树的一半时就出现了交集，也就是找到了最短距离。从这个例子是可以直观感受到，双向遍历是比传统传统单项遍历要好的。

但是，双向遍历的使用要有前提条件，也就是要提前知道【target】的位置，求【二叉树的最小深度】那道题就不适用，而【密码锁这道题】因为提前知道【target】的位置，所以可以使用双向遍历。

我在这给出使用双向遍历优化之后的代码：

 //将cur[j]向上拨一格
 string plusOne_(string cur, int j) {
     if (cur[j] == '9') cur[j] = '0';
     else cur[j] += 1;
     return cur;
 }
 ​
 //将cur[j]向下拨一格
 string minusOne_(string cur, int j) {
     if (cur[j] == '0') cur[j] = '9';
     else cur[j] -= 1;
     return cur;
 }
 ​
 //将问题抽象成图的问题，利用BFS算法解决问题
 int openLock(vector <string> &deadends, string target) {
     //需要先将死亡数字存储起来，为保证查找的时间复杂度为o(1),我们利用集合（哈希表）进行存储
     unordered_set <string> deads;
     for (string s: deadends) {
         deads.insert(s);
     }
     //记录穷举过的密码，防止走回头路
     unordered_set <string> q_start,q_target,visited;
     int step = 0;
     q_start.insert("0000");
     q_target.insert(target);
     //开始BFS遍历
     while (!q_start.empty() && !q_target.empty()) {
         //哈希表在遍历过程中不能修改，则新建一个哈希表temp存储扩散结果
         unordered_set <string> temp;
         
         //将q的所有节点进行扩散，先q_start,再q_target
         for(string s : q_start){
             if(deads.count(s) != 0) continue;
             if(q_target.count(s) != 0) return step; //说明出现了交集，直接返回结果
             visited.insert(s);
             
             //将每一个节点的未遍历节点加入temp中，作为下一层
             for(int j = 0; j < 4; j++){
                 string plusOne = plusOne_(s, j);
                 if(visited.count(plusOne) != 0) temp.insert(plusOne);   
                 string minusOne = minusOne_(s, j);
                 if(visited.count(plusOne) != 0) temp.insert(minusOne);  
             }
         }
         step++;
         q_start = q_target;
         q_target = temp;
     }
     //走到这里已经遍历完连通图的所有节点了，说明没有target
     return -1;
 }

这几天该准备我的期末考试了，所以每日分享的笔记篇幅会少一点，但是你们仍然可以借鉴与学习【手动狗头】。