基本介紹
- 中文名：廣度優先算法
- 外文名：Breadth-First Search
- 詞性：名詞
- 範疇：數學；計算機科學
思想,實現,分析,空間複雜度,時間複雜度,完全性,最佳解,套用,尋找連線元件,測試是否二分圖,套用於電腦遊戲中平面格線,
思想
BFS是一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位置，徹底地搜尋整張圖，直到找到結果為止。BFS並不使用經驗法則算法。
從算法的觀點，所有因為展開節點而得到的子節點都會被加進一個先進先出的佇列中。一般的實作里，其鄰居節點尚未被檢驗過的節點會被放置在一個被稱為open的容器中（例如佇列或是鍊表），而被檢驗過的節點則被放置在被稱為closed的容器中。（open-closed表）
實現
所謂廣度，就是一層一層的，向下遍歷，層層堵截，還是這幅圖，我們如果要是廣度優先遍歷的話，我們的結果是V1 V2 V3 V4 V5 V6 V7 V8。
1、訪問頂點vi ；
2、訪問vi 的所有未被訪問的鄰接點w1 ,w2 , …wk ；
3、依次從這些鄰接點（在步驟②中訪問的頂點）出發，訪問它們的所有未被訪問的鄰接點; 依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問；
分析
空間複雜度
因為所有節點都必須被儲存，因此BFS的空間複雜度為 O(|V| + |E|)，其中 |V| 是節點的數目，而 |E| 是圖中邊的數目。註：另一種說法稱BFS的空間複雜度為O(B^M)，其中 B 是最大分支係數，而 M 是樹的最長路徑長度。由於對空間的大量需求，因此BFS並不適合解非常大的問題。
時間複雜度
最差情形下，BFS必須尋找所有到可能節點的所有路徑，因此其時間複雜度為 O(|V| + |E|)，其中 |V| 是節點的數目，而 |E| 是圖中邊的數目。
完全性
廣度優先搜尋算法具有完全性。這意指無論圖形的種類如何，只要目標存在，則BFS一定會找到。然而，若目標不存在，且圖為無限大，則BFS將不收斂（不會結束）。
最佳解
若所有邊的長度相等，廣度優先搜尋算法是最佳解——亦即它找到的第一個解，距離根節點的邊數目一定最少；但對一般的圖來說，BFS並不一定回傳最佳解。這是因為當圖形為加權圖（亦即各邊長度不同）時，BFS仍然回傳從根節點開始，經過邊數目最少的解；而這個解距離根節點的距離不一定最短。這個問題可以使用考慮各邊權值，BFS的改良算法成本一致搜尋法（en:uniform-cost search）來解決。然而，若非加權圖形，則所有邊的長度相等，BFS就能找到最近的最佳解。
套用
廣度優先搜尋算法能用來解決圖論中的許多問題，例如：
尋找連線元件
由起點開始，執行廣度優先搜尋算法後所經過的所有節點，即為包含起點的一個連線元件。
測試是否二分圖
BFS 可以用以測試二分圖。從任一節點開始搜尋，並在搜尋過程中給節點不同的標籤。例如，給開始點標籤 0，開始點的所有鄰居標籤 1，開始點所有鄰居的鄰居標籤0……以此類推。若在搜尋過程中，任一節點有跟其相同標籤的鄰居，則此圖就不是二分圖。若搜尋結束時這種情形未發生，則此圖為一二分圖。
套用於電腦遊戲中平面格線
BFS 可用來解決電腦遊戲（例如即時策略遊戲）中找尋路徑的問題。在這個套用中，使用平面格線來代替圖形，而一個格子即是圖中的一個節點。所有節點都與它的鄰居（上、下、左、右、左上、右上、左下、右下）相接。
值得一提的是，當這樣使用BFS算法時，首先要先檢驗上、下、左、右的鄰居節點，再檢驗左上、右上、左下、右下的鄰居節點。這是因為BFS趨向於先尋找斜向鄰居節點，而不是四方的鄰居節點，因此找到的路徑將不正確。BFS 應該先尋找四方鄰居節點，接著才尋找斜向鄰居節點1。
