闊度優先搜揣

闊度優先搜揣演算法（英語：Breadth-First Search，縮寫為 BFS）， 閣譯作闊度優先搜揣，抑是橫向優先搜揣，是一種圖形搜揣演算法。簡單的講，BFS 是對根節點開始，沿著樹仔的闊度遍歷樹的節點。若所有的點均去予存取，則演算法內底止。闊度優先搜揣的實現一般所用 open-closed 表。

做法

BFS 是一種暴力搜揣演算法，目的是系統地展開並檢查圖中的所有節點，以走揣結果。嘛會使講，伊並無考慮結果的可能位址，徹底地搜揣規張圖，一直到揣著結果為止。BFS 並無使用經驗法則演算法。

對演算法的觀點，所有因為展開節點啊若得著的子節點乎攏會去予人加入來一个先進先出的佇列內底。一般的實作內底，其厝邊頭尾節點閣猶未予人檢驗過的節點會予人囥佇一个予人叫做是 _ open _ 的容器內底（譬如講在列抑是講連結串列）， 被檢驗過的節點予人囥佇咧予人叫做 _ closed _ 的容器內底。（open-closed 表）

實作方法

一 . 首先共根節點囥入去列中。 二 . 佇列中取出第一个節點，而且檢驗伊敢是目標。

• 若揣著目標，結束搜揣並回傳結果。
• 若無共所有猶未檢驗過直接子節點加入佇列中。

三 . 若在列為空，表示規張圖攏檢查過矣—— 亦即圖當中伊無欲走揣的目標。結束搜揣並回傳「揣無目標」。 四 . 重複步數字。

` ` ` s 為初初開始點 $ R :=\ { s \ } , Q :=\ { s \ } , T=\ emptyset $ while $ Q \ neq \ emptyset $ 對 Q 著較中選咧 v / * 若改選最後插入去 Q 的點，則為深度遍歷 , 會使講後進先出。* / if $ \ exists w \ in N ( v ) \ setminus R $ then / * N ( v ) : v 的厝邊隔壁點 * / $ Q :=Q \ cup \ { w \ } $ $ R :=R \ cup \ { w \ } $ $ T :=T \ cup \ { vw \ } $ else $ Q :=Q \ setminus \ { w \ } $ return H=( R , T ) ` ` `

C + + 的實作

( 這个例干焦針對 Binary Tree ) 定義一个結構體來表達一个較節點的結構：

遐爾，咱咧搜揣一樹仔的時陣，佇一个節點開始，會當代先取得的是伊的兩个子節點。比如講：

` ` ` A B C ` ` `

A 是第一个存取的，然後順序是 B 和 C；閣再來 B 的子節點，C 的子節點。按呢咱按怎來保證這个順序咧？

遮就應該用 queue 資料結構，因為乎 queue 會先進先出 ( first-in-first-out ) 的順序。

使用 C + + 的 STL 函式庫，下跤的程式碼會當幫助理解：

特性

空間複雜度

因為所有的儉點攏愛予人儉，所以 BFS 的空間複雜度做 $ O ( | V | + | E | ) $，其中 $ | V | $ 是節點的數目，而且 $ | E | $ 是圖中邊仔的數目。註：另外一種講法稱 BFS 的空間複雜度做 $ O ( B ^ { M } ) $，其中 B 是上大分支係數，而且 M 伊是樹仔的上長路徑長度。因為對空間的大量需求，所以 BFS 嘛無適合解非常大的問題，對類似的問題，應用 IDDFS 以達節省空間的效果。

時間複雜度

上䆀情形下，BFS 著愛揣所有到可能節點的所有的路草，所以其實時間複雜度做 $ O ( | V | + | E | ) $，其中 $ | V | $ 是節點的數目，而且 $ | E | $ 是圖中邊仔的數目。

完全性

廣度優先搜揣演算法具有完全性。這意指無論圖形的種類按怎，只要目標存在，著 BFS 一定會揣著。毋過，若目標無存在的，而且圖為無限大，著 BFS 將無收斂（袂煞）。

最佳解

所有的邊仔的長度相等，廣度優先搜揣演算法是最佳解—— 亦即伊揣著的第一个解，距離根節點的邊數目一定上少；但是一般的圖來講，BFS 並無一定回傳最佳會解。這是因為當圖形為加權圖（也就各邊的長度無仝）時，BFS 猶閣回傳對根節點開始，經過邊數目上少的解；毋過這个解距離根節點的距離無一定上短。這个問題會使使用考慮各邊權值，BFS 的改良演算法成本一致搜揣法來解決。毋過，若是非加權圖形，則所有邊的長度相等，BFS 就會當揣著最近的最佳解。

應用

闊度優先搜揣演算法會當用來解決圖論內底的真濟問題，比如講：

• 走揣圖當中所有的連接元件（Connected Component）。 隨个相連做元件是圖中的上大相連子圖。
• 走揣連接元件內底的所有節點。
• 走揣非加權圖中任兩點上短路徑。
• 試一圖是毋是有兩份圖。
• （Reverse）Cuthill–McKee 演算法

走揣連接元件

由起點開始，執行闊度優先搜揣演算法了後所經過的所有的點，即為包含起點的一個連接元件。

測試看覓是毋是二分圖

BFS 會當用測試二分圖。從任一節點開始搜揣，並且咧揣過程中予節點無仝款的標籤。比如講，予開始點標籤零，開始點的所有厝邊標籤一，開始點所有厝邊頭尾標籤零…… 以此類推。若佇咧搜揣過程，任一節點有佮其仝款標籤的厝邊，是按呢就毋是兩分圖。若搜揣結束的時陣這種情形無發生，是按呢圖為一兩分圖。

應用電腦遊戲中平面網格

BFS 通來解決電腦的遊戲（比如講時間的這个策略遊戲）中走揣路徑的問題。佇這个應用中，使用平面網格來代替圖形，啊若一个格仔即是圖中的一个節點。所有的點心攏佮伊的厝邊（上、落、倒、正、倒上、正手爿、倒落來、正下）相接。

價值咧講的是，做按呢用 BFS 算法的時陣，頭先愛先檢驗著、落、倒、厝邊頭尾節點，才閣檢驗倒上、正手爿、倒落來、厝邊隔壁節點。這是因為 BFS 較趨勢佇邊仔先揣厝邊頭尾節點，毋是四角的厝邊節點，所以揣著的路徑將無正確。BFS 應該愛先走揣四方厝邊節點，紲落來才來揣厝邊隔壁節點一。

參見

• 先驗演算法
• 深度優先搜揣

參考資料

• Thomas H . Cormen , Charles E . Leiserson , Ronald L . Rivest , and Clifford Stein ] , _ Introduction to Algorithms _ , Second Edition . MIT Press and McGraw-Hill , 兩千空一 . ISBN 空九二百六十二鋪三千二百九十三鋪七 . Section 二十二孵二 : Breadth-first search , pp .   五百三十一–五百三十九 .

外部連結

• （英文）資料結構佮演算法字典：闊度優先搜揣
• （英文）C + + Boost Graph 函式庫：闊度優先搜揣
• （英文）深度佮闊度優先搜揣：解說佮原始碼
• （英文）BFS 動畫說明