文章目錄
- BFS演算法框架
- 框架代碼
- 簡單題：二叉樹的最小高度
- 拔高題：解開密碼鎖的最少次數
- 一波優化：雙向BFS
BFS演算法框架
BFS演算法和DFS演算法屬于圖論演算法的范疇，DFS在前面回溯中，可以去看一下，
BFS演算法用于尋找兩點之間的最短路徑，
碧如說：尋找樹的最小高度（迭代法）、走迷宮、導航等問題，
這些問題看起來都會比較抽象，去做也是很抽象，
與其說演算法框架難寫，倒不如說是把實際問題轉化為演算法問題來的要難，
還記得我在圖論演算法那篇里面有講過：學習圖論演算法，最難的是要有用圖論演算法的意識，等下看了例題就知道了，
框架代碼
這個代碼其實就是微調一下圖的BFS遍歷，搞成個偽代碼的樣子，沒什么新鮮的，
int BFS(Node start,Node target){
/*
這是一個BFS演算法的代碼框架
return：回傳從start到target的最短步數
start：起始點
target：終點
*/
Queue<Node> q;
Set<Node> visited; //避免走回頭路
q.offer(start); //將起點加入佇列
visited.add(start);
int step = 0; //紀錄擴散的步數
while(q not empty){
int sz = q.size();
for(int i = 0; i<sz; i++){
Node cur = q.poll();
//判斷是否到終點
if(cur is target)
return step;
//將cur相鄰節點加入佇列
for(Node x: cur.adj()) //cur.adj()泛指與cur相鄰的節點
if(x not in visited){
q.offer(x);
visited.add(x);
}
}
step++; //更新步數
}
}
簡單題：二叉樹的最小高度
不難吧，用遞回的話一下就出來了，
不過現在不是在講BFS嘛，那就用BFS的方法吧，
起點是什么？起點是根節點，終點是什么？終點就是最靠近根節點的、兩個子節點都是Null的節點，
接下來，我們對上面的框架進行改造：
int minDepth(TreeNode root){
/*
這是一個求二叉樹最小高度的函式
return：二叉樹的最小高度
root：根節點
*/
if(root == NULL) return 0;
Queue<TreeNode> q;
q.offer(root); //將起點加入佇列
int depth = 1;
while(!q.isEmpty()){
int sz = q.size();
for(int i = 0; i<sz; i++){
TreeNode cur = q.poll();
//判斷是否到終點
if(cur.left == NULL && cur.right == NULL)
return depth;
//將cur相鄰節點加入佇列
if(cur.left != NULL)
q.offer(cur.left);
if(cur.right != NULL)
q.offer(cur.right);
}
depth++; //更新步數
}
return depth;
}
拔高題：解開密碼鎖的最少次數
你有一個帶有四個圓盤撥輪的輪盤鎖，每個撥輪都有“0-9”十個數字，旋轉沒有邊界限制，但是每次只能旋轉一個位置，輪盤鎖的初始位置是“0000”，現在給你一個密碼和一組死亡密碼（避免撥出的密碼），請你設計一個演算法，計算從初始狀態到撥出最終密碼所需要的最少次數，
抽象吧，就直接看這個題目，直接給我干懵逼了，
但是，不怕啊，前面不是說過了動態規劃類題目的解題步驟嘛，先把暴力解法畫出來，走通一條路，再優化，
那，暴力解法怎么解？真的，要不是有那個“死亡密碼組”的存在，還真的就很暴力了，
第一步，撥一下，不管會怎么樣，都得撥一下吧，這一下有八種可能了吧，
第二步，匹配，撥一下，對所有結果都進行一次的匹配，如果對上了，就回傳結果；如果對不上，回傳第一步再回圈，
注意點一：如果碰到死亡密碼，跳過，
注意點二：不要走回頭路，
注意點三：空間能省著用就省著用，
好，關鍵的一步來了，怎么將這個暴力演算法往圖論演算法的方向去引呢，
再看一下上面這個暴力演算法，不難看出來，這就是一個節點下面拖八個子節點的八叉樹，又是求最短距離，BFS，
int openLock(String[] deadends,String target){
//紀錄需要跳過的死亡密碼
Set<String> deads = new HashSet<>();
for(String s:deadends)
dead.add(s);
//紀錄已經窮舉過的密碼
set<String> visited = new HashSet<>();
Queue<String> q = new LinkedList<>();
//從起點開始啟動廣度優先搜索
int step = 0;
q.offer("0000");
visited.add("0000");
while(!q.isEmpty){
int sz = q.size();
for(int i = 0;i<sz;i++){
string cur = q.poll();
//判斷密碼是否合法
if(deads.contains(cur)
continue;
if(cur.equals(target))
return step;
}
//將一個節點的未遍歷相鄰節點加入佇列
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);
}
}
step++;
}
return -1;
}
上翻下翻的代碼：
String plusOne(String s,int j){
char[] ch = s.toCharArray();
if(ch[j] == '9')
ch[j] = '0';
else
ch[j] += 1;
return new String(ch);
}
String downOne(String s,int j){
char[] ch = s.toCharArray();
if(ch[j] == '0')
ch[j] = '9';
else
ch[j] -= 1;
return new String(ch);
}
一波優化：雙向BFS
上面的操作，簡化一下是這樣的：
從頂部藍色的節點，找底部紅色的節點，
所有節點都被遍歷了，
這時候我們換個思路，既然終點也是已知的，那就：
上下同步進行，在中間黑色節點的地方匯聚了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/262145.html
標籤：AI