廣度優先搜尋 (BFS)

圖的廣度優先搜尋會逐階存取頂點。第一層由起始頂點組成。每個下一個等級都由與前一個等級中的頂點相鄰的頂點組成。圖的廣度優先遍歷類似於樹遍歷中討論的樹的廣度優先遍歷。透過廣度優先遍歷樹，逐級存取節點。首先訪問根，然後訪問根的所有子代，然後訪問根的孫子，依此類推。類似地，圖的廣度優先搜尋首先訪問一個頂點，然後訪問它的所有相鄰頂點，然後訪問與這些頂點相鄰的所有頂點，依此類推。為了確保每個頂點僅被訪問一次，如果已經訪問過該頂點，則會跳過該頂點。

廣度優先搜尋演算法

從圖中的頂點 v 開始廣度優先搜尋的演算法在下面的程式碼中描述。

輸入：G = (V, E) 和起始頂點 v
輸出：一棵以 v
為根的 BFS 樹 1 樹 bfs(頂點 v) {
2 建立一個空隊列，用於儲存要存取的頂點；
3 將v加入隊列中；
4 馬克 v 訪問過；
5
6 while (隊列不為空) {
7 將一個頂點（例如 u）從佇列中出列；
8 將u加入到遍歷頂點清單中；
u
的每個鄰居 w 為 9 10 如果 w 尚未被訪問過 {
11 將w加入隊列中；
12 將 u 設定為樹中 w 的父級；
13 馬克曾經造訪過；
14 }
15 }
16 }

考慮下圖 (a) 的圖表。假設從頂點 0 開始廣度優先搜尋。首先訪問 0，然後訪問其所有鄰居 1、2 和 3，如下圖 (b) 所示。頂點 1 有三個鄰居：0、2 和 4。由於 0 和 2 已經被訪問過，所以您現在將只訪問 4，如下圖 (c) 所示。頂點 2 有 3 個鄰居：0、1 和 3，它們都已被訪問過。頂點 3 有 3 個鄰居：0、2 和 4，它們都已被訪問過。頂點 4 有兩個鄰居：1 和 3，它們都已被訪問過。至此，搜尋結束。

由於每條邊和每個頂點僅被訪問一次，因此bfs 方法的時間複雜度為O(|E| + |V|)，其中| E| 表示邊數，|V| 表示頂點數。

廣度優先搜尋的實現

bfs(int v) 方法在 Graph 介面中定義，並在 AbstractGraph.java 類別中實作（第 197-222 行）。它傳回以頂點 v 作為根的 Tree 類別的實例。此方法將搜尋到的頂點儲存在清單searchOrder（第198行）中，每個頂點的父級儲存在陣列parent（第199行）中，使用鍊錶作為佇列（第198行） 203–204），並使用isVisited 陣列來指示頂點是否已被存取（第207 行）。搜尋從頂點 v 開始。 v 被加入到第 206 行的佇列中，並被標記為已存取（第 207 行）。此方法現在檢查佇列中的每個頂點 u（第 210 行）並將其新增至 searchOrder（第 211 行）。此方法將u 的每個未訪問鄰居e.v 新增至隊列（第214 行），將其父級設定為u （第215 行） ，並將其標記為已存取（第216 行）。

下面的程式碼給出了一個測試程序，顯示從芝加哥開始的上圖中圖表的 BFS。

public class TestBFS {

    public static void main(String[] args) {
        String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"};

        int[][] edges = {
                {0, 1}, {0, 3}, {0, 5},
                {1, 0}, {1, 2}, {1, 3},
                {2, 1}, {2, 3}, {2, 4}, {2, 10},
                {3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5},
                {4, 2}, {4, 3}, {4, 5}, {4, 7}, {4, 8}, {4, 10},
                {5, 0}, {5, 3}, {5, 4}, {5, 6}, {5, 7},
                {6, 5}, {6, 7},
                {7, 4}, {7, 5}, {7, 6}, {7, 8},
                {8, 4}, {8, 7}, {8, 9}, {8, 10}, {8, 11},
                {9, 8}, {9, 11},
                {10, 2}, {10, 4}, {10, 8}, {10, 11},
                {11, 8}, {11, 9}, {11, 10}
        };

        Graph<string> graph = new UnweightedGraph(vertices, edges);
        AbstractGraph<string>.Tree bfs = graph.bfs(graph.getIndex("Chicago"));

        java.util.List<integer> searchOrders = bfs.getSearchOrder();
        System.out.println(bfs.getNumberOfVerticesFound() + " vertices are searched in this BFS order:");
        for(int i = 0; i 



<p>依下列順序搜尋 12 個頂點：<br>
 芝加哥 西雅圖 丹佛 堪薩斯市 波士頓 紐約<br>
 舊金山 洛杉磯 亞特蘭大 達拉斯 邁阿密 休士頓<br>
西雅圖的父級是芝加哥<br>
舊金山的父級是西雅圖<br>
洛杉磯的父級是丹佛<br>
丹佛的父母是芝加哥<br>
堪薩斯城的母校是芝加哥<br>
波士頓的父母是芝加哥<br>
紐約的父母是芝加哥<br>
亞特蘭大的母公司是堪薩斯城<br>
邁阿密的父母是亞特蘭大<br>
達拉斯的父母是堪薩斯城<br>
休士頓的父母是亞特蘭大</p>

<h2>
  
  
  BFS 的應用
</h2>

<p>DFS 解決的許多問題也可以使用 BFS 來解決。具體來說，BFS可以用來解決以下問題：</p>
<ul>
<li>偵測圖是否連通。如果圖中任兩個頂點之間存在路徑，則該圖是連通的。 </li>
<li>偵測兩個頂點之間是否存在路徑。 </li>
<li>找出兩個頂點之間的最短路徑。可以證明BFS樹中根到任意節點的路徑都是根到節點的最短路徑。 </li>
<li>找出所有連接的組件。連通分量是最大連通子圖，其中每對頂點都透過路徑連接。 </li>
<li>偵測圖中是否有環路。 </li>
<li>在圖中找到一個循環。 </li>
<li>測試圖是否為二分圖。 （如果圖的頂點可以分為兩個不相交的集合，並且同一集合中的頂點之間不存在邊，則該圖是二分圖。）</li>
</ul>

<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/172324339470608.png?x-oss-process=image/resize,p_40" class="lazy" alt="Breadth-First Search (BFS)"></p>


          

            
        </integer></string></string>

以上是廣度優先搜尋 (BFS)的詳細內容。更多資訊請關注PHP中文網其他相關文章！