Can you summarize the following document?
        
  BFS是一種盲目搜尋法,目的是系統地展開並檢查圖中的所有節點,以找尋結果。換句話說,它並不考慮結果的可能位址,徹底地搜尋整張圖,直到找到結果為止。BFS並不使用經驗法則演算法。  從演算法的觀點,所有因為展開節點而得到的子節點都會被加進一個先進先出的佇列中。一般的實作裡,其鄰居節點尚未被檢驗過的節點會被放置在一個被稱為 "open" 的容器中(例如佇列或是連結串列),而被檢驗過的節點則被放置在被稱為 "closed" 的容器中。(open-closed表) s為初始點

  formula_1

  定義一個結構體來表達一個節點的結構:  那麼,我們在搜尋一個樹的時候,從一個節點開始,能首先獲取的是它的兩個子節點。例如:  A是第一個訪問的,然後順序是B和C;然後再是B的子節點,C的子節點。那麼我們怎麼來保證這個順序呢?  這裡就應該用queue資料結構,因為queue採用先進先出( first-in-first-out )的順序。  使用C++的STL函式庫,下面的程式能幫助理解:

  

  因為所有節點都必須被儲存,因此BFS的空間複雜度為formula_8,其中formula_9是節點的數目,而formula_10是圖中邊的數目。注:另一種說法稱BFS的空間複雜度為formula_11,其中B是最大分支系數,而M是樹的最長路徑長度。由於對空間的大量需求,因此BFS並不適合解非常大的問題,對於類似的問題,應用IDDFS以達節省空間的效果。

  最差情形下,BFS必須尋找所有到可能節點的所有路徑,因此其時間複雜度為formula_8,其中formula_9是節點的數目,而formula_10是圖中邊的數目。

  廣度優先搜尋演算法具有完全性。這意指無論圖形的種類如何,只要目標存在,則BFS一定會找到。然而,若目標不存在,且圖為無限大,則BFS將不收斂(不會結束)。

  若所有邊的長度相等,廣度優先搜尋演算法是最佳解——亦即它找到的第一個解,距離根節點的邊數目一定最少;但對一般的圖來說,BFS並不一定回傳最佳解。這是因為當圖形為加權圖(亦即各邊長度不同)時,BFS仍然回傳從根節點開始,經過邊數目最少的解;而這個解距離根節點的距離不一定最短。這個問題可以使用考慮各邊權值,BFS的改良演算法成本一致搜尋法來解決。然而,若非加權圖形,則所有邊的長度相等,BFS就能找到最近的最佳解。

  廣度優先搜尋演算法能用來解決圖論中的許多問題,例如:

  由起點開始,執行廣度優先搜尋演算法後所經過的所有節點,即為包含起點的一個連線元件。

  BFS可以用以測試二分圖。從任一節點開始搜尋,並在搜尋過程中給節點不同的標籤。例如,給開始點標籤0,開始點的所有鄰居標籤1,開始點所有鄰居的鄰居標籤0......以此類推。若在搜尋過程中,任一節點有跟其相同標籤的鄰居,則此圖就不是二分圖。若搜尋結束時這種情形未發生,則此圖為一二分圖。

  BFS可用來解決電腦遊戲(例如即時策略遊戲)中找尋路徑的問題。在這個應用中,使用平面網格來代替圖形,而一個格子即是圖中的一個節點。所有節點都與它的鄰居(上、下、左、右、左上、右上、左下、右下)相接。  值得一提的是,當這樣使用BFS演算法時,首先要先檢驗上、下、左、右的鄰居節點,再檢驗左上、右上、左下、右下的鄰居節點。這是因為BFS趨向於先尋找斜向鄰居節點,而不是四方的鄰居節點,因此找到的路徑將不正確。BFS應該先尋找四方鄰居節點,接著才尋找斜向鄰居節點1。
廣度優先搜尋演算法(英語:Breadth-First Search,縮寫為BFS),又譯作寬度優先搜尋,或橫向優先搜尋,是一種圖形搜尋演算法。簡單的說,BFS是從根節點開始,沿著樹的寬度遍歷樹的節點。如果所有節點均被訪問,則演算法中止。廣度優先搜尋的實現一般採用open-closed表。