演算法淺談——走迷宮問題與廣度優先搜索 - - CodingNote.cc

與它相對的深度優先搜索，英文自然就是Depth First Search，簡寫成dfs。

所以如果在閱讀我或者其他人的程式碼時發現有個函數叫做bfs或者dfs，如果你能 ... 演算法淺談——走迷宮問題與廣度優先搜索 2020年3月12日 筆記 本文始發於個人公眾號：TechFlow，原創不易，求個關注 在之前周末LeetCode專欄當中，我們詳細描述了深度優先搜索和回溯法，所以今天我們繼續這個話題，來和大家聊聊搜索演算法的另一個分支，廣度優先搜索。

廣度優先搜索的英文是BreadthFirstSearch，簡寫為bfs。

與它相對的深度優先搜索，英文自然就是DepthFirstSearch，簡寫成dfs。

所以如果在閱讀我或者其他人的程式碼時發現有個函數叫做bfs或者dfs，如果你能回憶起這些英文縮寫，一定可以明白它們是什麼意思。

bfs與dfs 在講解bfs的概念之前，我們先來回顧一下dfs的概念，好有個對比。

通過之前的文章，我們已經知道了實現dfs往往需要使用遞歸。

我們在一次遞歸當中需要遍歷當前所有的決策，然後遞歸去執行這些決策。

如果這些決策會對未來的決策產生影響，那麼我們還需要使用回溯法，在決策遍歷結束之後，撤銷當前的操作。

所以我們有了dfs的模板程式碼： defdfs(n):ifn>depth:returnforiindecisions:do_decision(i)dfs(n+1)rollback(i) 假如我們有一棵樹，我們需要遍歷樹。

顯然由於樹是由節點組成的樹形結構，不是list結構，所以我們並不能直接用循環來遍歷。

為了避免重複，我們需要按照一定的順序在樹上遍歷。

最常用的就是使用dfs和bfs，我們先來看一下dfs怎麼解決這個問題。

套用一下上面的模板，我們可以很容易寫出來： defdfs(node):ifnodeisNone:returnforchildinnode.childs:print(child)dfs(child) 由於我們只需要遍歷節點，遍歷的過程並不會對後面的遍歷產生影響，所以我們不需要rollback這一步。

並且樹天然有結構，我們遞歸的順序剛好和樹本身的順序一致，都是從父節點往子節點遍歷。

所以並不需要其他的處理。

假如我們有這樣一棵樹： 使用dfs去遍歷它，得到的順序會是什麼？ 稍微帶入一下上面遍歷的邏輯應該就能想明白，它的順序是：A->B->C->D->E->F->G->H。

有沒有看出規律？其實dfs就是先一條路走到頭，然後再回頭去遍歷其他的路。

也就是當我們面臨多種決策的時候，我們優先往深度更大的方向前進。

而廣度優先搜索與它的邏輯剛好相反，從字面上意思我們也應該能猜得出來，bfs在搜索的時候傾向於先把當前所有的決策都做一遍，也就是它會往廣度更大的方向前進。

舉一個很簡單的例子，比如我們玩一個有多種結局的遊戲。

深度優先搜索就是不管三七二十一，先玩到通關再說，之後再來改變選擇去獲取其他的結局。

而廣度優先搜索則是在遊戲面臨選擇的時候不停地存檔，把所有可能性都遍歷一便，之後再一個一個讀取存檔，重複這個操作。

所以回到上面那個樹遍歷的問題，如果是bfs，它的遍歷順序顯然就是A->B->D->E->C->F->G->H。

實現方法 仔細分析會發現dfs是縱向的遍歷搜索樹，而bfs則是橫向進行的。

在實現dfs的時候，我們其實是借用了系統棧替我們存儲了之前遍歷的狀態。

而現在我們需要橫向遍歷的時候，顯然遞歸就不適用了，但是我們同樣需要一個數據結構來存儲遍歷時候的狀態，就好像遊戲存檔一樣。

再觀察一下這棵樹，A節點一共有3個分支B，D和E。

我們通過A節點可以拿到這三個節點。

之後我們要依次遍歷這三個節點，拿到它們的所有分支。

也就是說我們遍歷這BDE三個節點的順序就是我們遇見它的順序，我們把存儲狀態認為是寫入容器，而讀取的時候則認為從容器中彈出，那麼這個容器應該是先進先出的。

棧是先進後出的所以不滿足，而隊列是先進先出的，這正是我們需要的。

所以bfs是基於隊列實現的。

有了隊列之後，我們就可以把維護狀態的工作交給它，我們只需要關注遍歷單個節點的邏輯就好了。

因為隊列會替我們把這些節點串起來，當隊列當中沒有元素的時候，就說明我們已經遍歷結束了。

我們寫下模板程式碼： queue=Queue()whilenotqueue.empty():state=queue.front()queue.pop()print(state)fornew_stateinstate.new_states():queue.put(new_state) 很簡單對不對，使用隊列之後，遍歷的程式碼同樣沒有幾行。

關於隊列，實現的方法有很多。

只要掌握了原理，用什麼實現都是一樣的，list和鏈表都可以。

Python當中替我們實現了隊列，在Python3版本當中是queue，Python2則是Queue，這裡需要注意一下。

我使用的是Python3，所以就是queue，用法也很簡單： fromqueueimportQueueque=Queue()whilenotqueue.empty():state=queue.get()print(state)fornew_stateinstate.new_states():queue.put(new_state) 觀察一下就會發現，根據我的理解獲取隊列頭部的元素和頭部的元素彈出其實是兩個操作。

但是在queue庫當中，將它們合併成了一個。

也就是說我們在使用get方法獲取頭部元素的時候，它已經彈出隊列了，這點需要注意。

大多數情況下這點並沒有問題，但是有時候我們可能會希望先獲取，再來判斷要不要出列，這時候就不能使用這個庫了，可以考慮一下雙端都可以插入彈出的deque，或者是自己用list實現。

重點來了 如果大家在學習的過程當中抱著批判和求知的精神，肯定會有一個問題，就是我們為什麼要發明兩種遍歷方法呢？我們學會bfs究竟有什麼用處呢，難道dfs遞歸實現都不用自己維護數據結構不香嗎？ 這一點想想就知道非常重要，如果這點不明白，我們在實際當中遇到問題怎麼知道究竟用什麼演算法呢？但是遺憾的是，大多數教科書上並不會涉及這點，而是留給讀者自行思考，不得不說比較坑爹。

其實說起來只有一點差別，就是當我們搜索沒有結束就找到答案時，bfs可以提前結束，而dfs往往不能。

提前結束這個問題其實有兩個點，我們先來看其中比較簡單的一個：bfs實現通常是通過while循環，而不是使用遞歸。

那麼，當我們已經找到答案的時候，我們可以很簡單地通過break跳出循環，提前結束遍歷。

但是dfs則相對比較困難。

可能有些同學會說我們也可以在遞歸函數里return啊，難道不是一樣的么？ 其實還真的不太一樣，我們在遞歸當中執行return只能退出當前這一次執行，return之後會回到上層調用的地方，整個搜索過程並沒有結束。

舉個例子： defdfs(n):ifn>20:returnprint(n)foriinrange(n+1,50):dfs(i) 當n等於21的時候，會觸發n>20的條件，進行return，但是return之後會回到上一層循環的位置，後面i=21，22……50還是會執行。

也就是說雖然return了，但是整個遞歸過程沒有結束，結束的只是當前這一個節點。

而如果是bfs，由於我們是在循環當中執行的遍歷，我們直接break這個循環就可以結束整個bfs過程。

深入思考 如果我們只是想要搜索有沒有答案，或者是只想要獲得一個答案的時候，那麼其實dfs和bfs是差不多的。

雖然dfs會有無法直接退出的問題，但這並不是完全沒有辦法解決的，通過引入全局變數等方法，我們也可以變相提前退出，雖然稍微麻煩一點。

但如果我們想要尋找最優的答案，往往dfs就不適用了。

我們來看一個經典的例子，也是bfs的經典使用場景，即走迷宮問題。

############S#########E############# 上圖是一個非常簡單的迷宮，s表示起點，E表示終點。

#表示籬笆，也即不能走到的位置。

如果我們只是詢問這個迷宮是否有可行解，那麼dfs和bfs都是一樣的。

而且從編碼習慣上來說，我們可能更傾向於使用dfs來做回溯。

但如果我們想知道從起點走到終點的最短路徑的話，那麼這道題基本上就只能使用bfs了。

原因很簡單，因為當我們通過dfs找到終點的時候，我們並不能得知它是否是最短的路徑。

為了找出最短路徑，我們只能把所有通往終點的路徑都記錄下來，然後通過比較返回最短的。

這顯然是不科學的，因為我們額外遍歷了許多不必要的狀態，在一個搜索問題當中，這些不必要的狀態可能是非常多的。

而由於bfs是橫向遍歷，當找到終點的時候，就一定是最優解，所以直接break循環返回就行了，避免了大量沒有必要的遍歷。

也就是說能夠在第一時間找到答案，和最快到達答案的路徑，這個是bfs最大的特點。

這也是我們在問題當中使用bfs的本質原因。

初學者往往因為對於queue不熟悉而更傾向於使用dfs，而缺乏了對於這兩種搜索演算法本質的理解，除了演算法本身的原理，這也是非常重要的。

最後，我們附上bfs走迷宮的程式碼： fromqueueimportQueuefromcollectionsimportdefaultdictque=Queue()directions=[[0,1],[1,0],[0,-1],[-1,0]]visited=defaultdict(bool)defbfs(S,E,maze):#Sisstart,Eisend#maze地圖#visited記錄走過的位置n,m=len(maze),len(maze[0])que.push((S,[]))visited[S]=Truewhilenotque.empty():position,states=que.get()ifposition==E:states.append(E)returnstatesforxi,xjindirections:#拷貝，Python中list是引用傳遞，不使用copy會引起出錯cur=states.copy()x,y=position[0]+xi,position[i]+xjif0