廣度優(yōu)先算法
- 廣度優(yōu)先算法框架
- 廣度優(yōu)先算法運用
1. 廣度優(yōu)先算法框架
DFS（Deep First Search）深度優(yōu)先搜索雀哨，跟之前介紹的回溯算法沒啥差。
BFS（Breath First Search）廣度優(yōu)先搜索，和 DFS 主要區(qū)別是：BFS 找到的路徑一定是最短的，但代價就是空間復(fù)雜度比 DFS 大很多湾趾。
BFS 出現(xiàn)的常見場景芭商，其問題的本質(zhì)就是在一幅「圖」中找到從起點 start 到終點 target 的最近距離，如走迷宮搀缠、連連看等铛楣。
BFS 框架如下：
/**
* 計算從起點 start 到終點 target 的最近距離
*/
int BFS(Node start, Node target) {
Queue<Node> q; // 核心數(shù)據(jù)結(jié)構(gòu)
Set<Node> visited;// 避免走回頭路
q.offer(start); // 將起點加入隊列
visited.add(start);
int step = 0; // 記錄擴(kuò)散的步數(shù)
while (q not empty) {
int size = q.size();
// 將當(dāng)前隊列中的所有節(jié)點向四周擴(kuò)散
for (int i = 0; i < size; i++) {
Node cur = q.poll();
// 劃重點：這里判斷是否到達(dá)終點
if (cur is target) {
return step;
}
// 將 cur 的相鄰節(jié)點加入隊列
for (Node x : cur.adj()) {
if (x not in visited){
q.offer(x);
visited.add(x);
}
}
}
// 劃重點：更新步數(shù)在這里
step++;
}
}
}
上面值得注意的是，cur.adj() 泛指 cur 相鄰的節(jié)點艺普，如在二維數(shù)組中 cur 上下左右四面的位置就是相鄰節(jié)點簸州；visited 的作用是防止走回頭路，但在一般的二叉樹結(jié)構(gòu)中歧譬，無子節(jié)點到父節(jié)點的指針岸浑，不會走回頭路就不需要 visited。
2. 廣度優(yōu)先算法運用
2.1 二叉樹的最小深度
力扣 111 題如下：
首先瑰步，明確一下起點 start 和終點 target 是什么矢洲，顯然起點就是 root 根節(jié)點，終點就是最靠近根節(jié)點的葉子節(jié)點缩焦，葉子節(jié)點判斷如下：
// 葉子節(jié)點就是兩個子節(jié)點都是 null 的節(jié)點
if (cur.left == null && cur.right == null)
// 到達(dá)葉子節(jié)點
接著读虏，套用 BFS 框架實現(xiàn)如下：
/**
* 二叉樹最小深度
*/
public int minDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
// root 本身就是一層，depth 初始化為 1
int depth = 1;
while (!q.isEmpty()) {
int size = q.size();
// 將當(dāng)前隊列中的所有節(jié)點向四周擴(kuò)散
for (int i = 0; i < size; i++) {
TreeNode cur = q.poll();
// 劃重點：這里判斷是否到達(dá)終點
if (cur.left == null && cur.right == null) return depth;
// 將 cur 的相鄰節(jié)點加入隊列
if (cur.left != null) q.offer(cur.left);
if (cur.right != null) q.offer(cur.right);
}
// 劃重點：更新步數(shù)在這里
depth++;
}
return depth;
}
上面值得注意的是袁滥，depth 每增加一次盖桥，隊列中的所有節(jié)點都向前邁一步，保證了第一次到達(dá)終點時走的步數(shù)是最少的题翻。
2.2 打開轉(zhuǎn)盤鎖
力扣 752 題如下：
若不管不管 deadends 和 target 的限制揩徊，窮舉所有可能的密碼組合，考慮到共有4個位置藐握，每個位置轉(zhuǎn)動一次可以向上或向下轉(zhuǎn)動靴拱，即有8種可能，因此可以抽象成一幅圖猾普，每個節(jié)點有 8 個相鄰的節(jié)點，求最少轉(zhuǎn)動次數(shù)本谜，套用 BFS 框架如下：
/**
* BFS 框架初家，打印出所有可能的密碼
*/
void BFS(String target) {
Queue<String> q = new LinkedList<>();
q.offer("0000");
while (!q.isEmpty()) {
int size = q.size();
// 將當(dāng)前隊列中的所有節(jié)點向周圍擴(kuò)散
for (int i = 0; i < size; i++) {
String cur = q.poll();
// 判斷是否到達(dá)終點
System.out.print(cur);
// 將一個節(jié)點的相鄰節(jié)點加入隊列
for (int j = 0; j < 4; j++) {
String up = plusOne(cur, j);
String down = minusOne(cur, j);
q.offer(up);
q.offer(down);
}
}
// 在這里增加步數(shù)
}
return;
}
/**
* 將 s[i] 向上撥動一次
*/
String plusOne(String s, int i) {
char[] ch = s.toCharArray();
if (ch[i] == '9') ch[i] = '0';
else ch[i] += 1;
return new String(ch);
}
/**
* 將 s[i] 向下?lián)軇右淮? */
String minusOne(String s, int i) {
char[] ch = s.toCharArray();
if (ch[i] == '0') ch[i] = '9';
else ch[i] -= 1;
return new String(ch);
}
上面代碼能夠窮舉所有可能的密碼組合了，接下來處理題目中的如下問題：
- 會走回頭路乌助。(如從"0000"撥到"1000"溜在，等從隊列拿出"1000"時，還會撥出一個"0000"他托，產(chǎn)生死循環(huán))
- 終止條件掖肋。
- 對
deadends的處理。
修改代碼修復(fù)這些問題如下：
/**
* 打開轉(zhuǎn)盤鎖
*/
public int openLock(String[] deadends, String target) {
// 記錄需要跳過的死亡密碼
Set<String> deads = new HashSet<>();
for (String s : deadends) deads.add(s);
// 記錄已經(jīng)窮舉過的密碼赏参，防止走回頭路
Set<String> visited = new HashSet<>();
Queue<String> q = new LinkedList<>();
// 從起點開始啟動廣度優(yōu)先搜索
int step = 0;
q.offer("0000");
visited.add("0000");
while (!q.isEmpty()) {
int size = q.size();
// 將當(dāng)前隊列中的所有節(jié)點向周圍擴(kuò)散
for (int i = 0; i < size; i++) {
String cur = q.poll();
// 判斷是否到達(dá)終點
if (deads.contains(cur)) continue;
if (cur.equals(target)) return step;
// 將一個節(jié)點的相鄰節(jié)點加入隊列
for (int j = 0; j < 4; j++) {
String up = plusOne(cur, j);
if (!visited.contains(up)) {
q.offer(up);
visited.add(up);
}
String down = minusOne(cur, j);
if (!visited.contains(down)) {
q.offer(down);
visited.add(down);
}
}
}
// 在這里增加步數(shù)
step++;
}
// 如果窮舉完都沒找到目標(biāo)密碼志笼，那就是找不到了
return -1;
}
2.3 滑動謎題
力扣 773 題如下：
上面題目例子中沿盅，比如輸入 board = [[4,1,2],[5,0,3]]，可用如下直觀展示過程：
BFS 算法并不只是一個尋路算法纫溃，而是一種暴力搜索算法腰涧，只要涉及暴力窮舉的問題，BFS 就可以用紊浩。
這道題其實是一個 BFS 問題窖铡，每次先找到數(shù)字 0，然后和周圍的數(shù)字進(jìn)行交換坊谁，形成新的局面加入隊列... 當(dāng)?shù)谝淮蔚竭_(dá) target 時就得到了最少步數(shù)费彼。
這里的 board 是 2x3 的二維數(shù)組，可以壓縮成一個一維字符串口芍，然后寫一個映射對應(yīng)某一個索引上下左右的索引：
int[][] neighbor = new int[][]{
{1, 3},
{0, 4, 2},
{1, 5},
{0, 4},
{3, 1, 5},
{4, 2}
};
即在一維字符串中敌买，索引 i 在二維數(shù)組中的的相鄰索引為 neighbor[i]：
接著，就可以套用 BFS 算法框架實現(xiàn)代碼如下：
/**
* 滑動謎題
*/
public int slidingPuzzle(int[][] board) {
int m = 2, n = 3;
// 將 2x3 的數(shù)組轉(zhuǎn)化成字符串
StringBuilder sb = new StringBuilder();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
sb.append(board[i][j]);
}
}
String start = sb.toString();
String target = "123450";
// 記錄一維字符串的相鄰索引
int[][] neighbor = new int[][]{
{1, 3},
{0, 4, 2},
{1, 5},
{0, 4},
{3, 1, 5},
{4, 2}
};
// BFS 算法框架開始
Queue<String> q = new LinkedList<>();
Set<String> visited = new HashSet<>();
q.offer(start);
visited.add(start);
int step = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
String cur = q.poll();
// 判斷是否達(dá)到目標(biāo)局面
if (cur.equals(target)) return step;
// 找到數(shù)字 0 的索引
int index = 0;
while (cur.charAt(index) != '0') {
index++;
}
// 將數(shù)字 0 和相鄰的數(shù)字交換位置
for (int adj : neighbor[index]) {
char[] temp = cur.toCharArray();
temp[adj] = cur.charAt(index);
temp[index] = cur.charAt(adj);
String new_board = new String(temp);
// 防止走回頭路
if (!visited.contains(new_board)) {
q.offer(new_board);
visited.add(new_board);
}
}
}
step++;
}
return -1;
}
小結(jié)：
DFS 算法和回溯算法的核心思路是相同的阶界，邏輯上都是在遍歷一棵樹虹钮。
BFS 也是一個暴力搜索算法，只不過把遞歸改成了迭代膘融，利用一個隊列進(jìn)行窮舉而已芙粱。
參考鏈接：
