一、引言

????深度優先搜索（DFS）是一種在圖或樹中進行搜索的算法，它沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。當節點v的所有邊都已探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點并重復以上過程，整個進程反復進行直到所有節點都被訪問為止。
????DFS是一種盲目搜索，即它并不需要知道目標的位置，只是盡可能地遍歷所有可能的路徑。因此，它的搜索效率并不高，特別是在面對大規模數據時。然而，DFS可以找到目標值或解決目標問題，對于解決NP問題作用很大。
????此外，DFS如同數據結構中的棧結構，是一種后進先出的結構，導致了所有的點進入棧時有一個順序，我們稱之為 “DFS序”。

二、算法步驟

深度優先搜索算法的步驟如下：

1. 選取圖中某一頂點Vi為出發點，訪問并標記該頂點。
2. 以Vi為當前頂點，依次搜索Vi的每個鄰接點Vj，若Vj未被訪問過，則訪問和標記鄰接點Vj，若Vj已被訪問過，則搜索Vi的下一個鄰接點。
3. 以Vj為當前頂點，重復步驟2），直到圖中和Vi有路徑相通的頂點都被訪問為止。
4. 若圖中尚有頂點未被訪問過（非連通的情況下），則可任取圖中的一個未被訪問的頂點作為出發點，重復上述過程，直至圖中所有頂點都被訪問。

三、原理演示

遞歸實現

1. 選擇起始節點：從圖中的一個起始節點開始，將該節點標記為已訪問。
2. 遞歸探索鄰居節點：對于當前節點，遍歷它的鄰居節點。如果鄰居節點尚未被訪問，就遞歸地調用深度優先搜索函數，以此鄰居節點為新的起始節點，重復步驟1。
3. 回溯：當當前節點的所有鄰居節點都被訪問后，回溯到上一個節點，并繼續遍歷其未被訪問的鄰居節點。
4. 重復步驟2和3，直到圖中的所有節點都被訪問。

下面是遞歸實現深度優先搜索的示例代碼：

public void dfsRecursive(Node node, Set<Node> visited) {visited.add(node);System.out.print(node.value + " ");for (Node neighbor : node.neighbors) {if (!visited.contains(neighbor)) {dfsRecursive(neighbor, visited);}}
}

非遞歸實現（使用堆棧）

1. 選擇起始節點：從圖中的一個起始節點開始，將該節點標記為已訪問，并將它入棧。
2. 迭代遍歷：使用一個循環，不斷從棧中彈出節點，然后遍歷它的鄰居節點。
3. 探索鄰居節點：對于當前彈出的節點，遍歷其鄰居節點。如果鄰居節點尚未被訪問，就將其標記為已訪問并將其入棧。
4. 重復步驟2和3，直到棧為空。

下面是非遞歸實現深度優先搜索的示例代碼：

public void dfsIterative(Node start) {Stack<Node> stack = new Stack<>();Set<Node> visited = new HashSet<>();stack.push(start);visited.add(start);while (!stack.isEmpty()) {Node current = stack.pop();System.out.print(current.value + " ");for (Node neighbor : current.neighbors) {if (!visited.contains(neighbor)) {stack.push(neighbor);visited.add(neighbor);}}}
}

無論采用遞歸還是非遞歸方式，深度優先搜索的關鍵思想是深入到盡可能深的層級，直到無法再深入為止，然后回溯到上一個節點，繼續探索。這一過程不斷重復，直到遍歷整個圖。深度優先搜索對于解決路徑查找、拓撲排序、連通性檢測等問題都非常有用。

四、代碼實戰

以下是深度優先搜索算法的Java代碼實現：

import java.util.*;public class DFS {private int V; // 頂點數量private LinkedList<Integer> adj[]; // 鄰接表// 構造函數DFS(int v) {V = v;adj = new LinkedList[v];for (int i = 0; i < v; ++i) {adj[i] = new LinkedList();}}// 添加邊void addEdge(int v, int w) {adj[v].add(w);}// DFS函數void DFSUtil(int v, boolean visited[]) {// 標記當前節點為已訪問并輸出該節點visited[v] = true;System.out.print(v + " ");// 遞歸訪問與v節點相鄰的未訪問節點Iterator<Integer> i = adj[v].listIterator();while (i.hasNext()) {int n = i.next();if (!visited[n])DFSUtil(n, visited);}}// DFS函數void DFS(int v) {// 標記所有頂點為未訪問狀態boolean visited[] = new boolean[V];// 調用遞歸函數DFSUtil開始從頂點v進行DFS遍歷DFSUtil(v, visited);}
}

五、結論

我們一起來總結一下：
深度優先搜索在計算機科學中有著廣泛的應用，例如用于遍歷樹或圖的結構、查找路徑、解決優化問題等。它的優點在于空間復雜度相對較小，可以處理大規模的數據，同時可以避免搜索冗余的節點。然而，深度優先搜索也有其局限性，例如可能會陷入死循環或無法找到最優解，因此需要根據具體問題選擇合適的算法進行優化。
點贊收藏，富婆包養??