广度优先搜索
| 广度优先搜索 | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
 節點進行广度优先搜索的順序 | ||||||||||||
概况 | ||||||||||||
|
图与树 搜索算法 |
|---|
|
分类 |
|
相关主题 |
|
广度优先搜索算法（英语：Breadth-First-Search，縮寫為BFS），又譯作寬度優先搜索，或橫向優先搜索，是一種圖形搜索演算法。簡單的說，BFS是從根節點開始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。
目录
1 作法
2 實作方法
2.1 C 的實作
2.2 C++ 的實作
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=∅{displaystyle R:={s},Q:={s},T=emptyset }
while Q≠∅{displaystyle Qneq emptyset }
從Q中選一點
/* 若改選最後插入進Q的點，則為深度遍歷,可以说後進先出。*/
if ∃w∈N(v)∖R{displaystyle exists win N(v)setminus R}then /* N(v):v的邻接点 */
Q:=Q∪{w}{displaystyle Q:=Qcup {w}}
R:=R∪{w}{displaystyle R:=Rcup {w}}
T:=T∪{vw}{displaystyle T:=Tcup {vw}}
else Q:=Q∖{w}{displaystyle Q:=Qsetminus {w}}
return H=(R,T)
C 的實作
1 /*
2 ADDQ (Q, p) - p PUSH 入 Q
3 DELQ (Q) - POP Q 並返回 Q 頂
4 FIRSTADJ (G,v) - v 的第一個鄰接點，找不到則返回 -1
5 NEXTADJ (G,v) - v 的下一個鄰接點，找不到則返回 -1
6 VISIT (v) - 訪問 v
7 visited - 是否已訪問
8 */
9
10 // 廣度优先搜索算法
11 void BFS(VLink G, int v) {
12 int w;
13 VISIT(v); // 訪問 v 並入隊
14 visited[v] = 1;
15 ADDQ(Q, v);
16 // 對隊列 Q 的各元素
17 while (!EMPTYQ(Q)) {
18 v = DELQ(Q);
19 w = FIRSTADJ(G, v);
20 do {
21 // 進行訪問和入隊
22 if (visited[w] == 0) {
23 VISIT(w);
24 ADDQ(Q, w);
25 visited[w] = 1;
26 }
27 } while ((w = NEXTADJ(G, v)) != -1);
28 }
29 }
30
31 // 對圖G=(V,E)進行廣度優先搜索的主算法
32 void TRAVEL_BFS(VLink G, bool visited, int n) {
33 // 清零標記數組
34 for (int i = 0; i < n; ++i)
35 visited[i] = 0;
36 for (int i = 0; i < n; ++i)
37 if (visited[i] == 0)
38 BFS(G, i);
39 }
C++ 的實作
(這個例子僅針對Binary Tree)
定义一个结构体来表达一个節點的结构：
1 struct node {
2 int self; //数据
3 node *left; //左节点
4 node *right; //右节点
5 };
那么，我们在搜索一个树的时候，从一个节点开始，能首先获取的是它的两个子节点。例如：
A
B C
A是第一个访问的，然后顺序是B和C；然后再是B的子节点，C的子节点。那么我们怎么来保证这个顺序呢？
这里就应该用queue資料結構，因为queue採用先进先出( first-in-first-out )的顺序。
使用C++的STL函式庫，下面的程序能帮助理解：
1 std::queue<node *> visited, unvisited;
2 node nodes[9];
3 node *current;
4
5 unvisited.push(&nodes[0]); // 先把root放入unvisited queue
6
7 while (!unvisited.empty()) { // 只有unvisited不空
8 current = (unvisited.front()); // 目前應該檢驗的
9 if (current->left != NULL)
10 unvisited.push(current->left); // 把左邊放入queue中
11 if (current->right != NULL) // 右邊壓入。因為QUEUE是一個先進先出的結構构，所以即使後面再壓其他东西，依然會先訪問這個。
12 unvisited.push(current->right);
13 visited.push(current);
14 cout << current->self << endl;
15 unvisited.pop();
16 }
特性
空間複雜度
因為所有節點都必須被儲存，因此BFS的空間複雜度為O(|V|+|E|){displaystyle O(|V|+|E|)}
時間複雜度
最差情形下，BFS必須尋找所有到可能節點的所有路徑，因此其時間複雜度為O(|V|+|E|){displaystyle O(|V|+|E|)}
完全性
廣度優先搜索演算法具有完全性。這意指無論圖形的種類如何，只要目標存在，則BFS一定會找到。然而，若目標不存在，且圖為無限大，則BFS將不收斂（不會結束）。
最佳解
若所有邊的長度相等，廣度優先搜索演算法是最佳解——亦即它找到的第一個解，距離根節點的邊數目一定最少；但對一般的圖來說，BFS並不一定回傳最佳解。這是因為當圖形為加權圖（亦即各邊長度不同）時，BFS仍然回傳從根節點開始，經過邊數目最少的解；而這個解距離根節點的距離不一定最短。這個問題可以使用考慮各邊權值，BFS的改良演算法成本一致搜尋法來解決。然而，若非加權圖形，則所有邊的長度相等，BFS就能找到最近的最佳解。
廣度優先搜索演算法的應用
廣度優先搜索演算法能用來解決圖論中的許多問題，例如：
- 尋找圖中所有連接元件（Connected Component）。一個連接元件是圖中的最大相連子圖。
- 尋找連接元件中的所有節點。
- 尋找非加權圖中任兩點的最短路徑。
- 測試一圖是否為二分圖。
- （Reverse）Cuthill–McKee演算法
尋找連接元件
由起點開始，執行廣度優先搜索演算法後所經過的所有節點，即為包含起點的一個連接元件。
測試是否二分圖
BFS可以用以測試二分圖。從任一節點開始搜尋，並在搜尋過程中給節點不同的標籤。例如，給開始點標籤0，開始點的所有鄰居標籤1，開始點所有鄰居的鄰居標籤0……以此類推。若在搜尋過程中，任一節點有跟其相同標籤的鄰居，則此圖就不是二分圖。若搜尋結束時這種情形未發生，則此圖為一二分圖。
應用於電腦遊戲中平面網格
BFS可用來解決電腦遊戲（例如即時策略遊戲）中找尋路徑的問題。在這個應用中，使用平面網格來代替圖形，而一個格子即是圖中的一個節點。所有節點都與它的鄰居（上、下、左、右、左上、右上、左下、右下）相接。
值得一提的是，當這樣使用BFS演算法時，首先要先檢驗上、下、左、右的鄰居節點，再檢驗左上、右上、左下、右下的鄰居節點。這是因為BFS趨向於先尋找斜向鄰居節點，而不是四方的鄰居節點，因此找到的路徑將不正確。BFS應該先尋找四方鄰居節點，接著才尋找斜向鄰居節點1。
參見
- 先验算法
- 深度優先搜索
參考資料
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein], Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 22.2: Breadth-first search, pp. 531–539.
外部連結
（英文） 資料結構與演算法字典：廣度優先搜索
（英文） C++ Boost Graph函式庫：廣度優先搜索
（英文） 深度與廣度優先搜索：解釋與原始碼
（英文） BFS 動畫說明
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
