双向BFS算法学习
双向BFS算法学习
推荐练习题
力扣“127”题：单词接龙
“752”题：打开轮盘锁
这里推荐一篇力扣题解
双向BFS
这里使用打开轮盘锁的题干进行举例：
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，‘0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
分析
首先说明为什么使用双向BFS？
在这里我们可以把起点比做一个圆的圆心，我们使用BFS，就是对这个圆进行向外延伸，当延伸到目标点时，圆的面积就是时间复杂度，而我们采用双向BFS，就是从两
个点作为圆心，再进行延伸，当相交时，两个圆的面积小于只采用一个圆的面积（当目标点离起始点越远越明显）
这里我们与单向BFS的差别主要在下面几点：
- 这里有两个起始点，一个还是原来的起点0000，还有一个是我们的目标值，从这两个点开始发散的向四周发散的寻找，所以我们需要创建两个队列和两个保存已经遍历元素的哈希集
- 当一个队列的元素在另一个队列里面出现，这时说明两个点之间已经“打通”，找到了最短距离
- 这里注意我们尽量每次让两个队列平均的进行添加，这基于BFS的特性
- 这里结束循环的条件是两个队列都不为空，因为只要有一个位置空，就说明两点之间不能达到
代码
package Power;import java.util.*;public class doubleBFS {class Solution {String t, s;Set<String> set = new HashSet<>();public int openLock(String[] _ds, String _t) {s = "0000";t = _t;if (s.equals(t)) return 0;for (String d : _ds) set.add(d);if (set.contains(s)) return -1;int ans = bfs();return ans;}int bfs() {// d1 代表从起点 s 开始搜索（正向）// d2 代表从结尾 t 开始搜索（反向）Deque<String> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();/** m1 和 m2 分别记录两个方向出现的状态是经过多少次转换而来* e.g.* m1 = {"1000":1} 代表 "1000" 由 s="0000" 旋转 1 次而来* m2 = {"9999":3} 代表 "9999" 由 t="9996" 旋转 3 次而来*/Map<String, Integer> m1 = new HashMap<>(), m2 = new HashMap<>();d1.addLast(s);m1.put(s, 0);d2.addLast(t);m2.put(t, 0);/** 只有两个队列都不空，才有必要继续往下搜索* 如果其中一个队列空了，说明从某个方向搜到底都搜不到该方向的目标节点* e.g.* 例如，如果 d1 为空了，说明从 s 搜索到底都搜索不到 t，反向搜索也没必要进行了*/while (!d1.isEmpty() && !d2.isEmpty()) {int t = -1;if (d1.size() <= d2.size()) {t = update(d1, m1, m2);} else {t = update(d2, m2, m1);}if (t != -1) return t;}return -1;}int update(Deque<String> deque, Map<String, Integer> cur, Map<String, Integer> other) {int m = deque.size();while (m-- > 0) {String poll = deque.pollFirst();char[] pcs = poll.toCharArray();int step = cur.get(poll);// 枚举替换哪个字符for (int i = 0; i < 4; i++) {// 能「正向转」也能「反向转」，这里直接枚举偏移量 [-1,1] 然后跳过 0for (int j = -1; j <= 1; j++) {if (j == 0) continue;// 求得替换字符串 str// 这里使用的方法非常巧妙，把字符为0和9的特殊情况处理了int origin = pcs[i] - '0';// 取模处理9int next = (origin + j) % 10;// 如果为0.0-1为-1，进行处理，变成9if (next == -1) next = 9;char[] clone = pcs.clone();clone[i] = (char)(next + '0');String str = String.valueOf(clone);// 如果死亡数组里面包含，就重新执行循环if (set.contains(str)) continue;// 如果已经遍历过，就重新执行循环if (cur.containsKey(str)) continue;// 如果在「另一方向」找到过，说明找到了最短路，否则加入队列if (other.containsKey(str)) {return step + 1 + other.get(str);} else {deque.addLast(str);// 添加，更新步数cur.put(str, step + 1);}}}}return -1;}}
}