目錄

DFS的誕生——“不撞南墻不回頭”

DFS的核心機制——如何實現“回溯”？

DFS算法流程圖解（遞歸版）

C/C++代碼實現

DFS的應用

---

上一節我們學習了廣度優先搜索 (BFS)，它像水面的波紋一樣，一層一層地向外探索。今天，我們要學習它的“兄弟”算法——深度優先搜索 (Depth-First Search, DFS)，它體現了完全不同的探索哲學。

DFS的誕生——“不撞南墻不回頭”

再次回到那個巨大的迷宮入口。上次，我們的策略是“由近及遠”。但還有一種同樣符合直覺的策略，那就是“一條路走到黑”。

1. 你面前有多條路，隨便選 一條 走下去。

2. 在下一個路口，你再隨便選一條路，繼續 深入。

3. 你就這樣一直走，直到前面是死胡同（沒有新的路可走），或者回到了之前走過的路口。

4. 這時，你怎么辦？你會 原路返回 到上一個路口，看看那個路口還有沒有 其他沒走過的路。

5. 如果有，就選那條新路繼續深入。如果也沒有，就再退一步...

這種“勇往直前，走不通再退回來換條路”的探索策略，就是 深度優先搜索 (DFS)。“深度”指的就是它優先向“縱深方向”探索，直到無法再前進了，才回溯（backtrack）。

這個過程就像探險家在探索洞穴系統，他會沿著一個分支一直走到最深處，然后才返回來探索其他分支。

圖1??：DFS探索路徑的直觀感受

       (A) --1--> (B) --2--> (C) --3--> (D)  <-- 到達死胡同，開始回溯|          ^          ^|          |          '--5-- 回溯到C|          '--6-- 回溯到B'--4--> (E) ...

1, 2, 3是深入探索的路徑，4是回溯后嘗試的新路徑。

---

DFS的核心機制——如何實現“回溯”？

BFS的核心是隊列，因為它要保存“先來的先處理”。那么DFS呢？我們來分析一下“回溯”這個行為。

當你從 A -> B -> C，最后在 C 碰壁時，你需要返回到 B。當 B 的所有路都探索完后，你需要返回到 A。

這個返回的順序是 C -> B -> A。而你前進的順序是 A -> B -> C。

我們發現，這個路徑記錄有一個鮮明的特點：

最后記錄的路徑點，最先被拿出來用于回溯 (Last-In, First-Out)。這不就是 棧 (Stack) 的定義嗎！

所以，棧就是實現深度優先搜索“深入”和“回溯”特性的核心數據結構。

💡一個更優雅的實現：遞歸 (Recursion)

雖然我們可以手動維護一個棧來實現DFS，但在編程中，有一個更簡潔、更強大的工具天然就是用棧實現的——那就是函數調用。

當你調用一個函數 Func(A)，它內部又調用 Func(B)，Func(B) 內部又調用 Func(C) 時，計算機內部的“調用棧 (Call Stack)”會幫你記錄下這個調用鏈。

• Func(C) 執行完后，會自動返回到 Func(B) 的斷點處。

• Func(B) 執行完后，會自動返回到 Func(A) 的斷點處。

這不就完美地模擬了我們想要的“回溯”行為嗎？因此，遞歸是實現DFS最自然、最優雅的方式。我們可以把系統自帶的函數調用棧當作我們的“回溯”工具。

---

DFS算法流程圖解（遞歸版）

我們還是用上一節的圖，這樣你就可以清晰地對比BFS和DFS的差異。

      (A) --------- (B)|           /|          /|         /(D)       (C) --------- (E)|           /|          /'--------- (F)

我們同樣用鄰接表來表示它，并從頂點 A 開始遍歷。

準備工作:

• visited數組: [A:F, B:F, C:F, D:F, E:F, F:F] (F代表False)

---

第1步: DFS(A)

1. 主程序調用 DFS(A)。

2. 訪問 A，標記 visited[A] = T。

3. 查看 A 的鄰居：B 和 D。

4. 選擇第一個鄰居 B。B 未被訪問。

5. 遞歸調用 DFS(B)。DFS(A) 在這里暫停，等待 DFS(B) 返回。

狀態:

• 訪問順序: A

• visited: [A:T, B:F, ...]

• 調用棧: [ main, DFS(A) ]

---

第2步: DFS(B)

1. DFS(B) 開始執行。

2. 訪問 B，標記 visited[B] = T。

3. 查看 B 的鄰居：A 和 C。A 已被訪問，跳過。

4. 選擇下一個鄰居 C。C 未被訪問。

5. 遞歸調用 DFS(C)。DFS(B) 在此暫停。

狀態:

• 訪問順序: A, B

• visited: [A:T, B:T, C:F, ...]

• 調用棧: [ main, DFS(A), DFS(B) ]

---

第3步: DFS(C)

1. DFS(C) 開始執行。

2. 訪問 C，標記 visited[C] = T。

3. 查看 C 的鄰居：B, E, F。B 已被訪問，跳過。

4. 選擇下一個鄰居 E。E 未被訪問。

5. 遞歸調用 DFS(E)。DFS(C) 在此暫停。

狀態:

• 訪問順序: A, B, C

• visited: [A:T, B:T, C:T, E:F, ...]

• 調用棧: [ main, DFS(A), DFS(B), DFS(C) ]

---

第4步: DFS(E)

1. DFS(E) 開始執行。

2. 訪問 E，標記 visited[E] = T。

3. 查看 E 的鄰居：C, F。C 已被訪問。

4. 選擇下一個鄰居 F。F 未被訪問。

5. 遞歸調用 DFS(F)。DFS(E) 在此暫停。

狀態:

• 訪問順序: A, B, C, E

• visited: [..., E:T, F:F]

• 調用棧: [..., DFS(C), DFS(E) ]

---

第5步: DFS(F) 與回溯

1. DFS(F) 開始執行。

2. 訪問 F，標記 visited[F] = T。

3. 查看 F 的鄰居：C, E。都已被訪問。

4. DFS(F) 沒有可遞歸的調用了，執行完畢，返回。

5. 程序回到 DFS(E) 的暫停點。

狀態:

• 訪問順序: A, B, C, E, F

• visited: [..., E:T, F:T]

• 調用棧: [..., DFS(C), DFS(E) ] -> [..., DFS(C) ] (DFS(F)返回, DFS(E)恢復)

---

第6步: 繼續回溯

1. DFS(E) 恢復執行。它已經檢查完所有鄰居，執行完畢，返回。

2. 程序回到 DFS(C) 的暫停點。C 檢查過 E，現在檢查下一個鄰居 F。F 已被訪問。

3. DFS(C) 檢查完所有鄰居，執行完畢，返回。

4. 程序回到 DFS(B) 的暫停點。B 檢查完所有鄰居，執行完畢，返回。

5. 程序回到 DFS(A) 的暫停點。

狀態:

• 調用棧: [ main, DFS(A) ] (一層層返回)

---

第7步: 探索新分支

1. DFS(A) 恢復執行。它上次探索了鄰居 B。現在看下一個鄰居 D。

2. D 未被訪問。

3. 遞歸調用 DFS(D)。

狀態:

• 訪問順序: A, B, C, E, F, D

• visited: [..., D:T, ...]

• 調用棧: [ main, DFS(A), DFS(D) ]

---

DFS(D) 檢查其鄰居 A，已被訪問。DFS(D) 返回。DFS(A) 檢查完所有鄰居，返回 main。 所有頂點均被訪問，遍歷結束。

最終訪問順序: A -> B -> C -> E -> F -> D。

對比BFS的 A -> B -> D -> C -> E -> F，你會發現DFS的路徑明顯更“深”。

---

C/C++代碼實現

我們將使用上一節的鄰接表結構。

第一步: 核心遞歸函數 DFS 的框架

這個函數負責處理從單個頂點 v 開始的深度優先搜索。它需要知道整個圖 g，當前頂點 v，以及一個全局的 visited 數組來共享訪問狀態。

// 假設 MAX_VERTICES 和 AdjListGraph 結構體已經定義
#include <stdio.h>// v: 當前開始遍歷的頂點
// visited: 訪問標記數組
void DFS(AdjListGraph *g, int v, int visited[]) {// 核心邏輯將在這里實現
}

第二步: 訪問當前節點并探索鄰居

DFS的第一件事就是訪問當前節點，并標記它。然后，它需要遍歷當前節點的所有鄰居。

void DFS(AdjListGraph *g, int v, int visited[]) {// 1. 訪問并標記當前頂點printf("訪問頂點: %d\n", v);visited[v] = 1; // 1 表示已訪問// 2. 遍歷鄰接鏈表，準備對鄰居進行遞歸EdgeNode *p = g->adj_list[v].first_edge;while (p != NULL) {int w = p->neighbor_index; // 獲取鄰居頂點w// ... 對w進行處理 ...p = p->next;}
}

第三步: 加入遞歸調用

這是最關鍵的一步。在遍歷鄰居時，如果發現鄰居 w 沒有被訪問過，就對它發起遞歸調用，深入探索。

void DFS(AdjListGraph *g, int v, int visited[]) {printf("訪問頂點: %d\n", v);visited[v] = 1; EdgeNode *p = g->adj_list[v].first_edge;while (p != NULL) {int w = p->neighbor_index;// 核心：如果鄰居w未被訪問，就從w開始繼續深度優先搜索if (!visited[w]) {DFS(g, w, visited);}p = p->next;}
}

這個遞歸函數 DFS 已經完整了，非常簡潔，因為它巧妙地利用了函數調用棧。

第四步: 處理非連通圖的封裝函數

DFSTraverse 和BFS一樣，如果圖不連通，我們需要一個外部循環來確保每個連通分量都被遍歷到。

void DFSTraverse(AdjListGraph *g) {// 1. 初始化訪問標記數組int visited[MAX_VERTICES];for (int i = 0; i < g->num_vertices; i++) {visited[i] = 0; // 0 表示未訪問}// 2. 遍歷所有頂點for (int i = 0; i < g->num_vertices; i++) {// 如果頂點i還沒有在之前的搜索中被訪問過// 說明它屬于一個新的連通分量，從它開始新的DFSif (!visited[i]) {DFS(g, i, visited);}}
}

這個 DFSTraverse 就是我們提供給用戶調用的最終接口。

---

DFS的應用

DFS“不撞南墻不回頭”的特性，使得它特別適合解決與 “路徑”、“連通性”和“依賴關系” 相關的問題。

• 尋找路徑: DFS可以非常方便地找到從A到B的 一條 路徑（但不一定是最短的）。它探索的過程本身就在構建一條路徑。

• 檢測環 (Cycle Detection): 在有向圖中，如果在DFS的探索路徑上（即在當前的遞歸調用棧中）遇到了一個已經訪問過的頂點，那就說明發現了一個環。這是判斷程序或任務是否存在循環依賴的關鍵算法。

• 拓撲排序 (Topological Sort): 對于一個有向無環圖（比如課程的先修關系、項目的任務依賴），DFS可以輸出一個線性的序列，保證所有的依賴關系都得到滿足。

• 尋找連通分量 (Finding Connected Components): 我們上面寫的 DFSTraverse 實際上就在做這件事。每當外層循環啟動一次新的 DFS 調用，就意味著發現了一個新的連通分量。

DFS和BFS是圖論算法的左膀右臂，掌握了它們，你就真正地入門了圖的世界。