前言
作者之前也看過很多算法數，對於圖的這塊算法一直覺得似懂非懂。這次看《算法圖解》的時候才覺得豁然開朗。廢話不多說，讓我們開始學習：
廣度優先搜索是一種用於圖的查找算法，可幫助回答兩類問題。
- 第一類問題：從節點A出發，有前往節點B的路徑嗎？
- 第二類問題：從節點A出發，前往節點B的哪條路徑最短？
- 假設你經營著一個芒果農場，需要尋找芒果銷售商，以便將芒果賣給他。在Facebook，你與芒果銷售商有聯繫嗎？為此，你可在朋友中查找。
這種查找很簡單。首先，創建一個朋友名單。
然後，依次檢查名單中的每個人，看看他是否是芒果銷售商。
假設你沒有朋友是芒果銷售商，那麼你就必須在朋友的朋友中查找。
檢查名單中的每個人時，你都將其朋友加入名單。
這樣一來，你不僅在朋友中查找，還在朋友的朋友中查找。別忘了，你的目標是在你的人際關係網中找到一位芒果銷售商。因此，如果Alice不是芒果銷售商，就將其朋友也加入到名單中。
這意味著你將在她的朋友、朋友的朋友等中查找。使用這種算法將搜遍你的整個人際關係網，直到找到芒果銷售商。這就是廣度優先搜索算法。
剛才你看到了如何回答第一類問題，下面來嘗試回答第二類問題——誰是關係最近的芒果銷
售商。例如，朋友是一度關係，朋友的朋友是二度關係。
在你看來，一度關係勝過二度關係，二度關係勝過三度關係，以此類推。因此，你應先在一度關係中搜索，確定其中沒有芒果銷售商後，才在二度關係中搜索。廣度優先搜索就是這樣做的！
在廣度優先搜索的執行過程中，搜索範圍從起點開始逐漸向外延伸，即先檢查一度關係，再檢查二度關係。順便問一句：將先檢查Claire還是Anuj呢？Claire是一度關係，而Anuj是二度關係，因此將先檢查Claire，後檢查Anuj。
你也可以這樣看，一度關係在二度關係之前加入查找名單。
你按順序依次檢查名單中的每個人，看看他是否是芒果銷售商。這將先在一度關係中查找，再在二度關係中查找，因此找到的是關係最近的芒果銷售商。廣度優先搜索不僅查找從A到B的路徑，而且找到的是最短的路徑。
注意，只有按添加順序查找時，才能實現這樣的目的。換句話說，如果Claire先於Anuj加入名單，就需要先檢查Claire，再檢查Anuj。如果Claire和Anuj都是芒果銷售商，而你先檢查Anuj再檢查Claire，結果將如何呢？找到的芒果銷售商並非是與你關係最近的，因為Anuj是你朋友的朋友，而Claire是你的朋友。因此，你需要按添加順序進行檢查。有一個可實現這種目的的數據結構，那就是隊列（queue）。隊列是一種先進先出（First In First Out，FIFO）的數據結構，而棧是一種後進先出（Last In First Out，LIFO）的數據結構。知道隊列的工作原理後，我們來實現廣度優先搜索！
實現圖
首先，需要使用代碼來實現圖。圖由多個節點組成。
每個節點都與鄰近節點相連，如果表示類似於“你→Bob”這樣的關係呢？好在你知道的一種結構讓你能夠表示這種關係，它就是散列表！記住，散列表讓你能夠將鍵映射到值。在這裡，你要將節點映射到其所有鄰居。
表示這種映射關係的Python代碼如下。
注意，“你”被映射到了一個數組，因此graph[“you”]是一個數組，其中包含了“你”的所有鄰居。
圖不過是一系列的節點和邊，因此在Python中，只需使用上述代碼就可表示一個圖。那像下面這樣更大的圖呢？
表示它的Python代碼如下。
順便問一句：鍵—值對的添加順序重要嗎？換言之，如果你這樣編寫代碼：
而不是這樣編寫代碼：
對結果有影響嗎？
只要回顧一下前一章介紹的內容，你就知道沒影響。散列表是無序的，因此添加鍵—值對的順序無關緊要。
Anuj、Peggy、Thom和Jonny都沒有鄰居，這是因為雖然有指向他們的箭頭，但沒有從他們出發指向其他人的箭頭。這被稱為有向圖（directed graph），其中的關係是單向的。因此，Anuj是Bob的鄰居，但Bob不是Anuj的鄰居。無向圖（undirected graph）沒有箭頭，直接相連的節點互為鄰居。例如，下面兩個圖是等價的。
實現算法
先概述一下這種算法的工作原理。
首先，創建一個隊列。在Python中，可使用函數deque來創建一個雙端隊列。
別忘了，graph[“you”]是一個數組，其中包含你的所有鄰居，如[“alice”, “bob”, “claire”]。這些鄰居都將加入到搜索隊列中。
下面來看看其他的代碼。
最後，你還需編寫函數person_is_seller，判斷一個人是不是芒果銷售商，如下所示。
這個函數檢查人的姓名是否以m結尾：如果是，他就是芒果銷售商。這種判斷方法有點搞笑，但就這個示例而言是可行的。下面來看看廣度優先搜索的執行過程。
這個算法將不斷執行，直到滿足以下條件之一：
- 找到一位芒果銷售商；
- 隊列變成空的，這意味著你的人際關係網中沒有芒果銷售商。
Peggy既是Alice的朋友又是Bob的朋友，因此她將被加入隊列兩次：一次是在添加Alice的朋友時，另一次是在添加Bob的朋友時。因此，搜索隊列將包含兩個Peggy。
但你只需檢查Peggy一次，看她是不是芒果銷售商。如果你檢查兩次，就做了無用功。因此，檢查完一個人後，應將其標記為已檢查，且不再檢查他。如果不這樣做，就可能會導致無限循環。假設你的人際關係網類似於下面這樣。
檢查一個人之前，要確認之前沒檢查過他，這很重要。為此，你可使用一個列表來記錄檢查過的人。考慮到這一點後，廣度優先搜索的最終代碼如下。
運行時間
如果你在你的整個人際關係網中搜索芒果銷售商，就意味著你將沿每條邊前行（記住，邊是從一個人到另一個人的箭頭或連接），因此運行時間至少為O(邊數)。你還使用了一個隊列，其中包含要檢查的每個人。將一個人添加到隊列需要的時間是固定的，即為O(1)，因此對每個人都這樣做需要的總時間為O(人數)。所以，廣度優先搜索的運行時間為O(人數 + 邊數)，這通常寫作O(V + E)，其中V為頂點（vertice）數，E為邊數。
閱讀更多 看到他請叫他快去學習 的文章
