深度優先搜尋 (DFS)

圖的深度優先搜尋從圖中的一個頂點開始，在回溯之前盡可能存取圖中的所有頂點。
圖的深度優先搜尋類似於樹遍歷，樹遍歷中討論的樹的深度優先搜尋。對於樹，搜尋從根開始。在圖中，搜尋可以從任何頂點開始。

樹的深度優先搜尋首先訪問根，然後遞歸訪問根的子樹。類似地，圖的深度優先搜尋首先訪問一個頂點，然後遞歸地訪問與該頂點相鄰的所有頂點。不同之處在於該圖可能包含循環，這可能導致無限遞歸。為了避免這個問題，你需要追蹤已經訪問過的頂點。

該搜尋稱為深度優先，因為它盡可能在圖中搜尋「更深」。搜尋從某個頂點 v 開始。訪問完 v 後，它會訪問 v 的未訪問的鄰居。如果 v 沒有未造訪的鄰居，則搜尋回溯到到達 v 的頂點。我們假設圖是連通的，而搜尋開始從任意頂點可以到達所有頂點。

深度優先搜尋演算法

深度優先搜尋的演算法在下面的程式碼中描述。

輸入：G = (V, E) 和起始頂點 v
輸出：一棵以 v
為根的 DFS 樹 1 樹 dfs(頂點 v) {
2 訪問 v；
3 對於 v
的每個鄰居 w 4 if (w 尚未被訪問) {
5 將 v 設定為樹中 w 的父級；
6 dfs(w);
7 }
8 }

您可以使用名為isVisited的陣列來表示頂點是否已被存取。最初，對於每個頂點 i，isVisited[i] 為 false。一旦訪問了某個頂點（例如 v），isVisited[v] 就會設定為 true。

考慮下圖 (a) 的圖表。假設我們從頂點 0 開始深度優先搜尋。首先訪問 0，然後訪問它的任何鄰居，例如 1。現在訪問 1，如下圖 (b) 所示。頂點 1 有 3 個鄰居：0、2 和 4。由於 0 已經被訪問過，因此您將訪問 2 或 4。讓我們選擇 2。現在 2 被訪問，如下圖 (c) 所示。頂點 2 有 3 個鄰居：0、1 和 3。由於 0 和 1 已經被訪問過，所以選擇 3。現在訪問 3，如下圖 (d) 所示。此時，頂點已按以下順序被訪問過：

0、1、2、3

由於 3 的所有鄰居都已被訪問過，因此回溯到 2。由於 2 的所有頂點都已被訪問過，因此回溯到 1。4 與 1 相鄰，但 4 尚未被訪問過。因此，訪問4，如下圖(e)所示。由於 4 的所有鄰居都已訪問過，因此回溯到 1。
由於 1 的所有鄰居都已訪問過，所以回溯到 0。由於 0 的所有鄰居都已訪問過，因此搜索結束。

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

深度優先搜尋的實現

上面程式碼中的DFS演算法使用了遞迴。很自然地使用遞歸來實現它。或者，您可以使用堆疊。

dfs(int v) 方法在 AbstractGraph.java 的第 164-193 行中實作。它傳回 Tree 類別的實例，以頂點 v 作為根。此方法將搜尋到的頂點儲存在清單searchOrder （第165 行）中，將每個頂點的父級儲存在陣列parent（第166 行）中，並使用isVisited 陣列來指示是否已存取頂點（第171 行）。它呼叫輔助方法 dfs(v,parent, searchOrder, isVisited) 來執行深度優先搜尋（第 174 行）。

在遞歸輔助方法中，搜尋從頂點 u 開始。 u 新增至第 184 行的 searchOrder 並標記為已存取（第 185 行）。對於 u 的每個未訪問的鄰居，遞歸呼叫該方法來執行深度優先搜尋。當存取頂點 e.v 時，e.v 的父頂點儲存在 parent[e.v] 中（第 189 行）。當存取連通圖或連通組件中的所有頂點時，此方法會傳回。

下面的程式碼給出了一個測試程序，該程序顯示從芝加哥開始的上圖圖表的 DFS。從芝加哥出發的DFS示意圖如下圖所示。

public class TestDFS {

    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 dfs = graph.dfs(graph.getIndex("Chicago"));

        java.util.List<Integer> searchOrders = dfs.getSearchOrder();
        System.out.println(dfs.getNumberOfVerticesFound() + " vertices are searched in this DFS 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(dfs.getParent(i) != -1)
                System.out.println("parent of " + graph.getVertex(i) + " is " + graph.getVertex(dfs.getParent(i)));
    }

}

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

DFS的應用

深度優先搜尋可以用來解決很多問題，例如：

• 偵測圖是否連通。從任意頂點開始搜尋圖。如果搜尋到的頂點數與圖中的頂點數相同，則該圖是連通的。否則，圖形未連接。
• 偵測兩個頂點之間是否存在路徑。
• 尋找兩個頂點之間的路徑。
• 找出所有連接的組件。連通分量是最大連通子圖，其中每對頂點都透過路徑連接。
• 偵測圖中是否有環路。
• 在圖中找到一個循環。
• 尋找哈密頓路徑/循環。圖中的哈密爾頓路徑是只訪問圖中每個頂點一次的路徑。 哈密爾頓循環僅訪問圖中的每個頂點一次並返回起始頂點。

前六個問題可以使用AbstractGraph.java中的dfs方法輕鬆解決。要找到哈密頓路徑/循環，您必須探索所有可能的 DFS，以找到通往最長路徑的路徑。哈密​​頓路徑/循環有很多應用，包括解決著名的騎士之旅問題。

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