廣度優先搜尋 (BFS)-java教程-PHP中文網

廣度優先搜尋 (BFS)

王林

發布： 2024-08-10 06:43:10

原創

268 人瀏覽過

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

廣度優先搜尋演算法

從圖中的頂點 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，它們都已被訪問過。至此，搜尋結束。

Breadth-First Search (BFS)

由於每條邊和每個頂點僅被訪問一次，因此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 行）。

Breadth-First Search (BFS)

下面的程式碼給出了一個測試程序，顯示從芝加哥開始的上圖中圖表的 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 個頂點：
芝加哥西雅圖丹佛堪薩斯市波士頓紐約
舊金山洛杉磯亞特蘭大達拉斯邁阿密休士頓
西雅圖的父級是芝加哥
舊金山的父級是西雅圖
洛杉磯的父級是丹佛
丹佛的父母是芝加哥
堪薩斯城的母校是芝加哥
波士頓的父母是芝加哥
紐約的父母是芝加哥
亞特蘭大的母公司是堪薩斯城
邁阿密的父母是亞特蘭大
達拉斯的父母是堪薩斯城
休士頓的父母是亞特蘭大