查看“︁广度优先搜索”︁的源代码

{{NoteTA
|G1 = IT
}}
{{redirect|BFS}}
{{Algorithms
|Name=广度优先搜索
|Image=[[File:Breadth-first tree.svg|none|300px|節點搜索的順序]]
|Caption=節點進行广度优先搜索的順序
|Class=[[搜索演算法]]
|DataStructure=[[圖]]
|TimeComp=<math>O(|V|+|E|) = O(b^d)</math>
|SpaceComp=<math>O(|V|) = O(b^d)</math>
|Optimal=是
|Complete=是
}}
{{图搜索算法}}
'''广度优先搜索算法'''（{{lang-en|Breadth-first search}}，縮寫：'''BFS'''），又譯作'''寬度優先搜索'''，或'''橫向優先搜索'''，是一種[[搜索算法|圖形搜索演算法]]。簡單的說，BFS是從[[树_(数据结构)#术语|根節點]]開始，沿着树的宽度遍历树的[[节点]]。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。

== 作法 ==

BFS是一種[[暴力搜索]]算法，目的是系統地展開並檢查[[圖]]中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位址，徹底地搜索整張圖，直到找到結果為止。BFS並不使用[[啟發式搜索|經驗法則演算法]]。

從演算法的觀點，所有因為展開節點而得到的子節點都會被加進一個[[先進先出]]的[[队列]]中。一般的實作裡，其鄰居節點尚未被檢驗過的節點會被放置在一個被稱為 ''open'' 的容器中（例如佇列或是[[連結串列|-{zh-hans:链表; zh-hant:連結串列;}-]]），而被檢驗過的節點則被放置在被稱為 ''closed'' 的容器中。（open-closed表）
{|
|[[File:MapGermanyGraph.svg|thumb|250px|left|以[[德國]]城市為範例的地圖。城市間有數條道路相連接。]]
|[[File:GermanyBFS.svg|thumb|250px|center|從[[法蘭克福]]開始執行廣度優先搜索算法，所產生的廣度優先搜索算法樹。]]
|[[File:Animated BFS.gif|thumb|250px|right|廣度優先搜索算法的動畫範例]]
|}

== 實作方法 ==
# 首先將根節點放入队列中。
# 從队列中取出第一個節點，並檢驗它是否為目標。
#* 如果找到目標，則結束搜尋並回傳結果。
#* 否則將它所有尚未檢驗過的直接子節點加入队列中。
# 若队列為空，表示整張圖都檢查過了——亦即圖中沒有欲搜尋的目標。結束搜尋並回傳「找不到目標」。
# 重複步驟2。

 -{}-
  s为初始点
  <math>R:=\{ s \},Q:=\{ s \},T=\empty</math>
  while <math>Q \ne \empty</math>
      從Q中選一點 v /* 若改選<font color="#0000ff">最後</font>插入進Q的點，則為<font color="#0000ff">深度遍歷</font>,可以说<font color="#0000ff">後進先出</font>。*/
      if <math>\exists w \in N(v) \setminus R</math> then    /* N(v):v的邻接点 */
          <math>Q:=Q \cup \{ w \}</math>
          <math>R:=R \cup \{ w \}</math>
          <math>T:=T \cup \{ vw \}</math>
      else <math>Q:=Q \setminus \{ w \}</math>
  return H=(R,T)

=== C 的实例 ===
<syntaxhighlight lang="c" line="1">
/*
    ADDQ (Q, p) - p PUSH 入 Q
    DELQ (Q) - POP Q 并返回 Q 顶
    FIRSTADJ (G,v) - v 的第一个邻接点，找不到则返回 -1
    NEXTADJ (G,v) - v 的下一个邻接点，找不到则返回 -1
    VISIT (v) - 访问 v
    visited [] - 是否已访问
*/

// 广度优先搜索算法
void BFS(VLink G[], int v) {
    int w;
    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)进行广度优先搜索的主算法
void TRAVEL_BFS(VLink G[], bool visited[], int n) {
    // 清零标记数组
    for (int i = 0; i < n; ++i)
        visited[i] = 0;
    for (int i = 0; i < n; ++i)
        if (visited[i] == 0)
            BFS(G, i);
}
</syntaxhighlight>

=== C++ 的實作 ===
(這個例子僅針對Binary Tree)<br />
定义一个结构体来表达一个節點的结构：
<syntaxhighlight lang="cpp" line="1">
struct node {
    int self;     //数据
    node *left;   //左节点
    node *right;  //右节点
};
</syntaxhighlight>
那么，我们在搜索一个树的时候，从一个节点开始，能首先获取的是它的两个子节点。例如：

    A
 B     C

A是第一个访问的，然后顺序是B和C；然后再是B的子节点，C的子节点。那么我们怎么来保证这个顺序呢？

这里就应该用queue資料結構，因为queue採用先进先出( first-in-first-out )的顺序。

使用C++的STL函式庫，下面的-{zh-hans:程序; zh-hant:程式碼;}-能帮助理解：
<syntaxhighlight lang="cpp" line="1">
 std::queue<node *> visited, unvisited;
node nodes[9];
node *current;

unvisited.push(&nodes[0]); // 先把root放入unvisited queue

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 << current->self << endl;
    unvisited.pop();
}
</syntaxhighlight>

== 特性 ==
=== 空間複雜度 ===
因為所有節點都必須被儲存，因此BFS的空間複雜度為<math> O(|V| + |E|) </math>，其中<math> |V| </math>是節點的數目，而<math> |E| </math>是圖中邊的數目。註：另一種說法稱BFS的空間複雜度為<math>O(B^M)</math>，其中B是最大[[分支因子|分支係數]]，而M是樹的最長路徑長度。由於對空間的大量需求，因此BFS並不適合解非常大的問題，對於類似的問題，應用[[迭代深化深度优先搜索|IDDFS]]以達節省空間的效果。

=== 時間複雜度 ===
最差情形下，BFS必須尋找所有到可能節點的所有路徑，因此其時間複雜度為<math> O(|V| + |E|) </math>，其中<math> |V| </math>是節點的數目，而<math> |E| </math>是圖中邊的數目。

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

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

== 應用 ==
廣度優先搜索演算法能用來解決圖論中的許多問題，例如：

* 尋找圖中所有連接元件（Connected Component）。一個連接元件是圖中的最大相連子圖。
* 尋找連接元件中的所有節點。
* 尋找非加權圖中任兩點的最短路徑。
* 測試一圖是否為[[二分圖]]。
* [[Cuthill-McKee演算法|（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.&nbsp;531–539.

== 外部連結 ==
* {{en}} [http://www.nist.gov/dads/HTML/breadthfirst.html 資料結構與演算法字典：廣度優先搜索] {{Wayback|url=http://www.nist.gov/dads/HTML/breadthfirst.html |date=20070401190651 }}
* {{en}} [http://www.boost.org/libs/graph/doc/breadth_first_search.html C++ Boost Graph函式庫：廣度優先搜索] {{Wayback|url=http://www.boost.org/libs/graph/doc/breadth_first_search.html |date=20070329004953 }}
* {{en}} [http://www.kirupa.com/developer/actionscript/depth_breadth_search.htm 深度與廣度優先搜索：解釋與原始碼] {{Wayback|url=http://www.kirupa.com/developer/actionscript/depth_breadth_search.htm |date=20070410024509 }}
* {{en}} [http://www.cs.duke.edu/csed/jawaa/BFSanim.html BFS 動畫說明] {{Wayback|url=http://www.cs.duke.edu/csed/jawaa/BFSanim.html |date=20070403052434 }}

{{-}}
{{算法}}

[[Category:圖演算法]]
[[Category:搜尋演算法]]