一、廣度優先搜尋（BFS，Breadth First Search）
直覺地講，它其實就是一種“地毯式”層層推進的搜尋政策，即先查找離起始頂點最近的，然後是次近的，依次往外搜尋。
假設我們有這麼一個圖，裡面有A、B、C、D、E、F、G、H 8 個頂點，點和點之間的聯系如下圖所示， 對這個圖進行廣度優先的周遊。
依賴隊列（Queue），先進先出（FIFO）。
一層一層地把與某個點相連的點放入隊列中，處理節點的時候正好按照它們進入隊列的順序進行。 第一步，選擇一個起始頂點，讓我們從頂點 A 開始。把 A 壓入隊列，标記它為通路過（用紅色标記）。
第二步，從隊列的頭取出頂點 A，列印輸出到結果中，同時将與它相連的尚未被通路過的點按照字母大 小順序壓入隊列，同時把它們都标記為通路過，防止它們被重複地添加到隊列中。
第三步，從隊列的頭取出頂點 B，列印輸出它，同時将與它相連的尚未被通路過的點（也就是 E 和 F） 壓入隊列，同時把它們都标記為通路過。
第四步，繼續從隊列的頭取出頂點 D，列印輸出它，此時我們發現，與 D 相連的頂點 A 和 F 都被标記 通路過了，是以就不要把它們壓入隊列裡。
第五步，接下來，隊列的頭是頂點 G，列印輸出它，同樣的，G 周圍的點都被标記通路過了。我們不做 任何處理。
第六步，隊列的頭是 E，列印輸出它，它周圍的點也都被标記為通路過了，我們不做任何處理。
第七步，接下來輪到頂點 F，列印輸出它，将 C 壓入隊列，并标記 C 為通路過。
第八步，将 C 從隊列中移出，列印輸出它，與它相連的 H 還沒被通路到，将 H 壓入隊列，将它标記為 通路過。
第九步，隊列裡隻剩下 H 了，将它移出，列印輸出它，發現它的鄰居都被通路過了，不做任何事情。
第十步，隊列為空，表示所有的點都被處理完畢了，程式結束。
最短路徑問題
廣度優先搜尋，一般用來解決最短路徑的問題。
時間複雜度
（1）鄰接表
每個頂點都需要被通路一次，時間複雜度是 O(V)；相連的頂點（也就是每條邊）也都要被通路一次，加 起來就是 O(E)。是以整體時間複雜度就是 O(V+E)。
（2）鄰接矩陣
V 個頂點，每次都要檢查每個頂點與其他頂點是否有聯系，是以時間複雜度是 O( V平方 )。
應用
廣度優先的搜尋可以同時從起始點和終點開始進行，稱之為雙端 BFS。這種算法往往可以大大地提高搜尋的效率。
社交網絡可以用圖來表示。這個問題就非常适合用圖的廣度優先搜尋算法來解決，因為廣度優先搜尋是 層層往外推進的。首先，周遊與起始頂點最近的一層頂點，也就是使用者的一度好友，然後再周遊與使用者 距離的邊數為 2 的頂點，也就是二度好友關系，以及與使用者距離的邊數為 3 的頂點，也就是三度好友關系。