本文始發于個人公衆号：TechFlow，原創不易，求個關注
在之前周末LeetCode專欄當中，我們較長的描述了深度優先搜尋和回溯法，是以今天我們繼續這個話題，來和大家聊聊搜尋算法的另一個分支，廣度優先搜尋。
廣度優先搜尋的英文是Breadth First Search，簡寫為bfs。與它相對的深度優先搜尋，英文自然就是Depth First Search，簡寫成dfs。是以如果在閱讀我或者其他人的代碼時發現有個函數叫做bfs或者dfs，如果你能回憶起這些英文縮寫，一定可以明白它們是什麼意思。
bfs與dfs
在講解bfs的概念之前，我們先來回顧一下dfs的概念，好有個對比。
通過之前的文章，我們已經知道了實作dfs往往需要使用遞歸。我們在一次遞歸當中需要周遊目前所有的決策，然後遞歸去執行這些決策。如果這些決策會對未來的決策産生影響，那麼我們還需要使用回溯法，在決策周遊結束之後，撤銷目前的操作。
是以我們有了dfs的模闆代碼：
def dfs(n):
if n > depth:
return
for i in decisions:
do_decision(i)
dfs(n+1)
rollback(i)
假如我們有一棵樹，我們需要周遊樹。顯然由于樹是由節點組成的樹形結構，不是list結構，是以我們并不能直接用循環來周遊。為了避免重複，我們需要按照一定的順序在樹上周遊。最常用的就是使用dfs和bfs，我們先來看一下dfs怎麼解決這個問題。
套用一下上面的模闆，我們可以很容易寫出來：
def dfs(node):
if node is None:
return
for child in node.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()
while not queue.empty():
state = queue.front()
queue.pop()
print(state)
for new_state in state.new_states():
queue.put(new_state)
很簡單對不對，使用隊列之後，周遊的代碼同樣沒有幾行。關于隊列，實作的方法有很多。隻要掌握了原理，用什麼實作都是一樣的，list和連結清單都可以。Python當中替我們實作了隊列，在Python3版本當中是queue，Python2則是Queue，這裡需要注意一下。我使用的是Python3，是以就是queue，用法也很簡單：
from queue import Queue
que = Queue()
while not queue.empty():
state = queue.get()
print(state)
for new_state in state.new_states():
queue.put(new_state)
觀察一下就會發現，根據我的了解擷取隊列頭部的元素和頭部的元素彈出其實是兩個操作。但是在queue庫當中，将它們合并成了一個。也就是說我們在使用get方法擷取頭部元素的時候，它已經彈出隊列了，這點需要注意。大多數情況下這點并沒有問題，但是有時候我們可能會希望先擷取，再來判斷要不要出列，這時候就不能使用這個庫了，可以考慮一下雙端都可以插入彈出的deque，或者是自己用list實作。
重點來了
如果大家在學習的過程當中抱着批判和求知的精神，肯定會有一個問題，就是我們為什麼要發明兩種周遊方法呢？我們學會bfs究竟有什麼用處呢，難道dfs遞歸實作都不用自己維護資料結構不香嗎？
這一點想想就知道非常重要，如果這點不明白，我們在實際當中遇到問題怎麼知道究竟用什麼算法呢？但是遺憾的是，大多數教科書上并不會涉及這點，而是留給讀者自行思考，不得不說比較坑爹。
其實說起來隻有一點差别，就是當我們搜尋沒有結束就找到答案時，bfs可以提前結束，而dfs往往不能。
提前結束這個問題其實有兩個點，我們先來看其中比較簡單的一個：bfs實作通常是通過while循環，而不是使用遞歸。那麼，當我們已經找到答案的時候，我們可以很簡單地通過break跳出循環，提前結束周遊。但是dfs則相對比較困難。可能有些同學會說我們也可以在遞歸函數裡return啊，難道不是一樣的麼？
其實還真的不太一樣，我們在遞歸當中執行return隻能退出目前這一次執行，return之後會回到上層調用的地方，整個搜尋過程并沒有結束。舉個例子：
def dfs(n):
if n > 20:
return
print(n)
for i in range(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走迷宮的代碼：
from queue import Queue
from collections import defaultdict
que = Queue()
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
visited = defaultdict(bool)
def bfs(S, E, maze):
# S is start, E is end
# maze 地圖
# visited 記錄走過的位置
n, m = len(maze), len(maze[0])
que.push((S, []))
visited[S] = True
while not que.empty():
position, states = que.get()
if position == E:
states.append(E)
return states
for xi, xj in directions:
# 拷貝，Python中list是引用傳遞，不使用copy會引起出錯
cur = states.copy()
x, y = position[0] + xi, position[i] + xj
if 0 < x < n and 0 < y < m and maze[x][y] != '#' and not visited[(x, y)]:
visited[(x, y)] = True
cur.append((x, y))
que.put(((x, y), cur))
return []
到這裡關于bfs算法的介紹就告一段落了，在後面LeetCode專題，我們會結合具體的題目為大家介紹更多bfs的用法。感興趣的同學可以小小期待一下哦。
如果覺得有所收獲，請順手點個在看或者轉發吧，你們的舉手之勞對我來說很重要。
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)