雙向BFS算法學習

推薦練習題
力扣“127”題：單詞接龍
“752”題：打開輪盤鎖
這里推薦一篇力扣題解
雙向BFS
這里使用打開輪盤鎖的題干進行舉例：

你有一個帶有四個圓形撥輪的轉(zhuǎn)盤鎖。每個撥輪都有10個數(shù)字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每個撥輪可以自由旋轉(zhuǎn)：例如把 ‘9’ 變?yōu)?‘0’，‘0’ 變?yōu)?‘9’ 。每次旋轉(zhuǎn)都只能旋轉(zhuǎn)一個撥輪的一位數(shù)字。

鎖的初始數(shù)字為 ‘0000’ ，一個代表四個撥輪的數(shù)字的字符串。

列表 deadends 包含了一組死亡數(shù)字，一旦撥輪的數(shù)字和列表里的任何一個元素相同，這個鎖將會被永久鎖定，無法再被旋轉(zhuǎn)。

字符串 target 代表可以解鎖的數(shù)字，你需要給出解鎖需要的最小旋轉(zhuǎn)次數(shù)，如果無論如何不能解鎖，返回 -1 。

分析

首先說明為什么使用雙向BFS？
在這里我們可以把起點比做一個圓的圓心，我們使用BFS，就是對這個圓進行向外延伸，當延伸到目標點時，圓的面積就是時間復雜度，而我們采用雙向BFS，就是從兩
個點作為圓心，再進行延伸，當相交時，兩個圓的面積小于只采用一個圓的面積（當目標點離起始點越遠越明顯）

這里我們與單向BFS的差別主要在下面幾點：

1. 這里有兩個起始點，一個還是原來的起點0000，還有一個是我們的目標值，從這兩個點開始發(fā)散的向四周發(fā)散的尋找，所以我們需要創(chuàng)建兩個隊列和兩個保存已經(jīng)遍歷元素的哈希集
2. 當一個隊列的元素在另一個隊列里面出現(xiàn)，這時說明兩個點之間已經(jīng)“打通”，找到了最短距離
3. 這里注意我們盡量每次讓兩個隊列平均的進行添加，這基于BFS的特性
4. 這里結(jié)束循環(huán)的條件是兩個隊列都不為空，因為只要有一個位置空，就說明兩點之間不能達到

代碼

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 代表從結(jié)尾 t 開始搜索（反向）Deque<String> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();/** m1 和 m2 分別記錄兩個方向出現(xiàn)的狀態(tài)是經(jīng)過多少次轉(zhuǎn)換而來* e.g.* m1 = {"1000":1} 代表 "1000" 由 s="0000" 旋轉(zhuǎn) 1 次而來* m2 = {"9999":3} 代表 "9999" 由 t="9996" 旋轉(zhuǎn) 3 次而來*/Map<String, Integer> m1 = new HashMap<>(), m2 = new HashMap<>();d1.addLast(s);m1.put(s, 0);d2.addLast(t);m2.put(t, 0);/** 只有兩個隊列都不空，才有必要繼續(xù)往下搜索* 如果其中一個隊列空了，說明從某個方向搜到底都搜不到該方向的目標節(jié)點* 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++) {// 能「正向轉(zhuǎn)」也能「反向轉(zhuǎn)」，這里直接枚舉偏移量 [-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);// 如果死亡數(shù)組里面包含，就重新執(zhí)行循環(huán)if (set.contains(str)) continue;// 如果已經(jīng)遍歷過，就重新執(zhí)行循環(huán)if (cur.containsKey(str)) continue;// 如果在「另一方向」找到過，說明找到了最短路，否則加入隊列if (other.containsKey(str)) {return step + 1 + other.get(str);} else {deque.addLast(str);// 添加，更新步數(shù)cur.put(str, step + 1);}}}}return -1;}}
}