廣度優先搜尋 (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 < searchOrders.size(); i++)
            System.out.print(graph.getVertex(searchOrders.get(i)) + " ");
        System.out.println();

        for(int i = 0; i < searchOrders.size(); i++)
            if(bfs.getParent(i) != -1)
                System.out.println("parent of " + graph.getVertex(i) + " is " + graph.getVertex(bfs.getParent(i)));
    }

}

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

BFS 的應用

DFS 解決的許多問題也可以使用 BFS 來解決。具體來說，BFS可以用來解決以下問題：

• 偵測圖是否連通。如果圖中任兩個頂點之間存在路徑，則該圖是連通的。
• 偵測兩個頂點之間是否存在路徑。
• 找出兩個頂點之間的最短路徑。可以證明BFS樹中根到任意節點的路徑都是根到節點的最短路徑。
• 找出所有連接的組件。連通分量是最大連通子圖，其中每對頂點都透過路徑連接。
• 偵測圖中是否有環路。
• 在圖中找到一個循環。
• 測試圖是否為二分圖。 （如果圖的頂點可以分為兩個不相交的集合，並且同一集合中的頂點之間不存在邊，則該圖是二分圖。）

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