广度优先搜索- 维基百科，自由的百科全书

BFS可用來解決電腦遊戲（例如即時策略遊戲）中找尋路徑的問題。

在這個應用中，使用平面網格來代替圖形，而一個格子即是圖中的一個節點。

所有節點都與它的 ... 廣度優先搜尋 維基百科，自由的百科全書 跳至導覽 跳至搜尋 廣度優先搜尋節點進行廣度優先搜尋的順序概況類別搜尋演算法資料結構圖複雜度平均時間複雜度 O ( | V | + | E | ) = O ( b d ) {\displaystyleO(|V|+|E|)=O(b^{d})} 最壞時間複雜度 O ( | V | + | E | ) = O ( b d ) {\displaystyleO(|V|+|E|)=O(b^{d})} 空間複雜度 O ( | V | ) = O ( b d ) {\displaystyleO(|V|)=O(b^{d})} 最佳解是完全性是相關變數的定義 圖與樹搜尋演算法 α–β A* B*（英語：B*） 回溯 集束（英語：Beamsearch） 貝爾曼-福特 最佳優先（英語：Best-firstsearch） 雙向 Borůvka（英語：Borůvka'salgorithm） 分支限界（英語：Branchandbound） BFS 大英博物館 D*（英語：D*） DFS 深度限制（英語：Depth-limitedsearch） 迪傑斯特拉 Edmonds（英語：Edmonds'algorithm） 弗洛伊德 邊緣搜尋 爬山 IDA*（英語：IterativedeepeningA*） 迭代加深 Johnson（英語：Johnson'salgorithm） 跳點（英語：Jumppointsearch） 克魯斯克爾 詞典BFS（英語：Lexicographicbreadth-firstsearch） LPA*（英語：LifelongPlanningA*） 普里姆 SMA*（英語：SMA*） 最短路徑快速 分類 圖演算法 搜尋演算法 演算法列表（英語：Listofalgorithms） 相關主題 動態規劃 圖的遍歷 樹的遍歷 閱論編 廣度優先搜尋演算法（英語：Breadth-FirstSearch，縮寫為BFS），又譯作寬度優先搜尋，或橫向優先搜尋，是一種圖形搜尋演算法。

簡單的說，BFS是從根節點開始，沿著樹的寬度遍歷樹的節點。

如果所有節點均被存取，則演算法中止。

廣度優先搜尋的實現一般採用open-closed表。

目次 1作法 2實作方法 2.1C的實例 2.2C++的實作 3特性 3.1空間複雜度 3.2時間複雜度 3.3完全性 3.4最佳解 4廣度優先搜索演算法的應用 4.1尋找連接元件 4.2測試是否二分圖 4.3應用於電腦遊戲中平面網格 5參見 6參考資料 7外部連結 作法[編輯] BFS是一種暴力搜尋演算法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。

換句話說，它並不考慮結果的可能位址，徹底地搜尋整張圖，直到找到結果為止。

BFS並不使用經驗法則演算法。

從演算法的觀點，所有因為展開節點而得到的子節點都會被加進一個先進先出的佇列中。

一般的實作裡，其鄰居節點尚未被檢驗過的節點會被放置在一個被稱為open的容器中（例如佇列或是連結串列），而被檢驗過的節點則被放置在被稱為closed的容器中。

（open-closed表） 以德國城市為範例的地圖。

城市間有數條道路相連接。

從法蘭克福開始執行廣度優先搜尋演算法，所產生的廣度優先搜尋演算法樹。

廣度優先搜尋演算法的動畫範例 實作方法[編輯] 首先將根節點放入佇列中。

從佇列中取出第一個節點，並檢驗它是否為目標。

如果找到目標，則結束搜尋並回傳結果。

否則將它所有尚未檢驗過的直接子節點加入佇列中。

若佇列為空，表示整張圖都檢查過了——亦即圖中沒有欲搜尋的目標。

結束搜尋並回傳「找不到目標」。

重複步驟2。

s為初始點 R := { s } , Q := { s } , T = ∅ {\displaystyleR:=\{s\},Q:=\{s\},T=\emptyset} while Q ≠ ∅ {\displaystyleQ\neq\emptyset} 從Q中選一點v/*若改選最後插入進Q的點，則為深度遍歷,可以說後進先出。

*/ if ∃ w ∈ N ( v ) ∖ R {\displaystyle\existsw\inN(v)\setminusR} then/*N(v):v的鄰接點*/ Q := Q ∪ { w } {\displaystyleQ:=Q\cup\{w\}} R := R ∪ { w } {\displaystyleR:=R\cup\{w\}} T := T ∪ { v w } {\displaystyleT:=T\cup\{vw\}} else Q := Q ∖ { w } {\displaystyleQ:=Q\setminus\{w\}} returnH=(R,T) C的實例[編輯] /* ADDQ(Q,p)-pPUSH入Q DELQ(Q)-POPQ并返回Q顶 FIRSTADJ(G,v)-v的第一个邻接点，找不到则返回-1 NEXTADJ(G,v)-v的下一个邻接点，找不到则返回-1 VISIT(v)-访问v visited[]-是否已访问 */ //广度优先搜索算法 voidBFS(VLinkG[],intv){ intw; VISIT(v);//访问v并入队 visited[v]=1; ADDQ(Q,v); //对队列Q的各元素 while(!EMPTYQ(Q)){ v=DELQ(Q); w=FIRSTADJ(G,v); do{ //进行访问和入队 if(visited[w]==0){ VISIT(w); ADDQ(Q,w); visited[w]=1; } }while((w=NEXTADJ(G,v))!=-1); } } //对图G=(V,E)进行广度优先搜索的主算法 voidTRAVEL_BFS(VLinkG[],boolvisited[],intn){ //清零标记数组 for(inti=0;ivisited,unvisited; nodenodes[9]; node*current; unvisited.push(&nodes[0]);//先把root放入unvisitedqueue while(!unvisited.empty()){//只有unvisited不空 current=(unvisited.front());//目前應該檢驗的 if(current->left!=NULL) unvisited.push(current->left);//把左邊放入queue中 if(current->right!=NULL)//右邊壓入。

因為QUEUE是一個先進先出的結構构，所以即使後面再壓其他东西，依然會先訪問這個。

unvisited.push(current->right); visited.push(current); cout<self<