深度優先搜索（DFS）完全解析：從原理到 Java 實戰

@TOC
作為一名程序員，你是否遇到過需要在復雜的圖結構中尋找路徑、檢測環，或者進行樹遍歷的問題？深度優先搜索（Depth-First Search, DFS）作為一種經典的圖遍歷算法，能夠輕松應對這些場景。在 CSDN 社區中，技術文章的受歡迎程度往往取決于內容的實用性、代碼的可讀性以及圖文結合的講解方式。因此，本文將為你帶來一篇深入淺出、圖文并茂、代碼詳盡的 DFS 指南，涵蓋原理、Java 實現、應用場景和實戰示例，確保你不僅理解 DFS，還能立刻上手應用！

---

什么是深度優先搜索（DFS）？

深度優先搜索（DFS）是一種用于遍歷或搜索樹或圖的算法。它的核心思想是：從一個起始節點開始，沿著一條路徑盡可能深入地探索，直到無法繼續前進時，再回溯到上一個分叉點，嘗試其他路徑。用一句話概括：DFS 是一種“先走到盡頭再回頭”的搜索策略。

與廣度優先搜索（BFS）“層層擴展”的方式不同，DFS 更像是一個勇敢的探險家，優先深入某一條路，直到碰壁才返回。這種特性使得 DFS 在某些問題（如路徑查找、環檢測）中特別高效。

---

DFS 的工作原理（圖解）

為了讓你直觀理解 DFS 的執行過程，我們以一個簡單的圖為例：

圖結構：0/ \1---2|3

• 邊表示：0-1, 0-2, 1-2, 2-3
• DFS 從節點 0 開始：
  1. 訪問 0
  2. 從 0 進入 1，訪問 1
  3. 從 1 進入 2，訪問 2
  4. 從 2 進入 3，訪問 3
  5. 3 沒有未訪問的鄰居，回溯到 2
  6. 2 沒有其他未訪問鄰居，回溯到 1
  7. 1 沒有其他未訪問鄰居，回溯到 0
  8. 0 的所有鄰居已訪問，結束

訪問順序：0 -> 1 -> 2 -> 3

下圖展示了 DFS 的過程（灰色表示已訪問）：

初始狀態       訪問 0        訪問 1        訪問 2        訪問 30            0*           0*           0*           0*/ \          / \          / \          / \          / \1---2        1---2        1*--2        1*--2*       1*--2*|            |            |            |            |3            3            3            3*           3*

這種“一條路走到黑”的方式，正是 DFS 的精髓。

---

DFS 的應用場景

DFS 在實際開發中用途廣泛，以下是幾個典型場景：

1. 路徑查找：在迷宮或圖中尋找從起點到終點的所有可能路徑。
2. 環檢測：判斷圖中是否存在環，常用于依賴關系分析。
3. 拓撲排序：對有向無環圖（DAG）進行排序，例如任務調度。
4. 連通性分析：在無向圖中找出所有連通分量。
5. 樹遍歷：實現二叉樹的先序、中序、后序遍歷。

---

用 Java 實現 DFS

在 Java 中，DFS 通常通過遞歸或顯式棧實現。這里我們以鄰接表表示圖，并用遞歸方式實現 DFS，因為它代碼簡潔且符合直覺。

完整代碼示例

以下是一個基于鄰接表的 DFS 實現，包含詳細注釋：

import java.util.*;public class DFSGraph {private int V; // 圖的節點數private LinkedList<Integer>[] adj; // 鄰接表表示圖// 構造函數，初始化圖public DFSGraph(int v) {V = v;adj = new LinkedList[v];for (int i = 0; i < v; i++) {adj[i] = new LinkedList<>(); // 為每個節點初始化鄰接表}}// 添加邊（無向圖）public void addEdge(int v, int w) {adj[v].add(w); // v -> wadj[w].add(v); // w -> v（無向圖需添加雙向邊）}// DFS 核心遞歸方法private void dfsUtil(int v, boolean[] visited) {visited[v] = true; // 標記當前節點為已訪問System.out.print(v + " "); // 訪問節點（這里打印）// 遍歷當前節點的所有鄰接節點for (int neighbor : adj[v]) {if (!visited[neighbor]) { // 如果鄰接節點未被訪問dfsUtil(neighbor, visited); // 遞歸訪問}}}// DFS 入口方法public void DFS(int start) {boolean[] visited = new boolean[V]; // 記錄訪問狀態dfsUtil(start, visited); // 從起始節點開始 DFS}// 測試代碼public static void main(String[] args) {DFSGraph graph = new DFSGraph(5); // 創建一個 5 個節點的圖// 添加邊graph.addEdge(0, 1);graph.addEdge(0, 2);graph.addEdge(1, 3);graph.addEdge(2, 4);graph.addEdge(3, 4);System.out.println("從節點 0 開始的 DFS 遍歷：");graph.DFS(0);}
}

運行結果

從節點 0 開始的 DFS 遍歷：
0 1 3 4 2

代碼詳解

1. 圖的表示：
   • 使用 LinkedList<Integer>[] adj 作為鄰接表，adj[i] 存儲節點 i 的所有鄰接節點。
   • V 表示節點總數。
2. 添加邊：
   • addEdge 方法為無向圖添加雙向邊。
3. DFS 實現：
   • dfsUtil 是遞歸核心，標記并訪問當前節點，然后遞歸處理未訪問的鄰接節點。
   • DFS 方法初始化 visited 數組并啟動遍歷。
4. main 方法：
   • 構建一個 5 節點圖，添加邊后從節點 0 開始 DFS。

---

DFS 的時間與空間復雜度

• 時間復雜度：O(V + E)
  • V 是節點數，E 是邊數，DFS 需要訪問所有節點和邊。
• 空間復雜度：O(V)
  • 遞歸棧的深度最多為 V，加上 visited 數組的空間。

---

實戰項目：迷宮求解

讓我們通過一個迷宮問題展示 DFS 的應用。假設有一個 4x4 的迷宮，0 表示通路，1 表示墻，目標是從 (0,0) 到 (3,3) 找一條路徑。

迷宮表示

0 1 0 0
0 1 0 1
0 0 0 0
1 1 0 0

Java 代碼

public class MazeSolver {static int[][] maze = {{0, 1, 0, 0},{0, 1, 0, 1},{0, 0, 0, 0},{1, 1, 0, 0}};static int N = 4;static int[][] path = new int[N][N]; // 記錄路徑// 四個方向：上、右、下、左static int[] dx = {-1, 0, 1, 0};static int[] dy = {0, 1, 0, -1};public static boolean solveMaze(int x, int y) {// 到達終點 (3,3)if (x == N - 1 && y == N - 1) {path[x][y] = 1;return true;}// 檢查當前位置是否合法if (isSafe(x, y)) {path[x][y] = 1; // 標記為路徑的一部分// 嘗試四個方向for (int i = 0; i < 4; i++) {int nextX = x + dx[i];int nextY = y + dy[i];if (solveMaze(nextX, nextY)) {return true;}}// 回溯：如果當前路徑不通，撤銷標記path[x][y] = 0;}return false;}// 檢查坐標是否有效public static boolean isSafe(int x, int y) {return x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 0;}public static void main(String[] args) {if (solveMaze(0, 0)) {System.out.println("找到路徑：");for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {System.out.print(path[i][j] + " ");}System.out.println();}} else {System.out.println("無解");}}
}

輸出結果

找到路徑：
1 0 0 0
1 0 0 0
1 1 1 1
0 0 0 1

解析

• DFS 策略：從 (0,0) 開始，嘗試四個方向（上、右、下、左），遇到墻或邊界回溯。
• 路徑記錄：path 數組標記走過的位置，成功到達 (3,3) 時返回路徑。

---

總結與互動

通過這篇文章，你應該已經掌握了 DFS 的原理、Java 實現以及實戰應用。無論是圖遍歷還是迷宮求解，DFS 都展現了其簡潔而強大的能力。為了加深理解，不妨試試以下問題：

• 如何用 DFS 檢測圖中的環？

• 如果用棧而非遞歸實現 DFS，會是什么樣？

  歡迎在評論區分享你的代碼或疑問，一起探討 DFS 的更多玩法！如果覺得這篇博客對你有幫助，記得點贊和收藏哦！