導讀：從廣度到深度，探索圖的遍歷奧秘

大家好，很高興又和大家見面啦！！！

在上一篇中，我們共同揭開了廣度優先搜索（BFS）的神秘面紗：它以“分層擴散”的方式遍歷圖結構，借助隊列實現層序遍歷，擅長解決最短路徑和連通性分析問題（例如社交網絡中的好友推薦）。BFS如同一束光波，由近及遠均勻覆蓋每個角落，確保無遺漏地探索所有可能性。

而今天，我們將潛入另一種經典策略——深度優先搜索（DFS）。與BFS的“廣撒網”不同，DFS更像一位執著探險家，認準一條路走到盡頭，再回溯尋找新路徑。這種策略在迷宮探索、拓撲排序、環路檢測等場景中大放異彩。

為何需要DFS？關鍵差異一目了然👇

• 遍歷邏輯：BFS用隊列實現“先進先出”，逐層掃描；DFS用棧（或遞歸）實現“后進先出”，縱深突破。

• 適用場景：BFS適合最短路徑，DFS擅長深入探測結構特性（如回溯問題、圖的連通分量統計）。

• 空間效率：BFS在稠密圖中可能內存暴增，DFS的空間消耗通常與路徑深度成正比，更適合樹形結構。

本文你將收獲：

• DFS核心思想：從二叉樹的先序/后序遍歷，推演至圖的深度優先法則，圖解“一條路走到黑+回溯”的精髓。
• 代碼與邏輯全解：遞歸與非遞歸實現對比，visited數組如何避免重復訪問，連通圖與非連通圖的遍歷陷阱。
• 深度優先生成樹：如何用DFS“繪制”圖的骨架，鄰接矩陣與鄰接表為何導致生成樹不唯一？
• 實戰思考：DFS在有向圖（如依賴解析）與無向圖中的不同表現，強連通分量的秘密。

閱讀建議：搭配上一篇“BFS詳解”食用更佳！通過對比兩大算法，你將真正掌握“何時用BFS，何時選DFS”的決策智慧。文末附生成樹案例詳解，幫助你將抽象理論轉化為直觀洞察。🚀

現在，讓我們一起潛入圖論的深海，揭開DFS的層層奧秘吧！

一、深度優先搜索

深度優先搜索（Depth-First-Search, DFS），簡單的理解就是盡可能深的進行遍歷，用一句話來描述就是一條路走到黑。

在二叉樹的遍歷算法中，按照遍歷的方式，我們可以將其分為4類：

• 先根遍歷：根—>左—>右
• 中根遍歷：左—>根—>右
• 后根遍歷：左—>右—>根
• 層序遍歷：分層遍歷

其中層序遍歷實際上就是我們所說的：廣度優先搜索（BFS）在樹中的一種實際應用。在上一篇的內容中我們已經詳細介紹，這里就不再贅述。

下面我們就來分析一下其他的三種遍歷；

• 先根遍歷的核心是：先訪問根結點，再訪問子樹，對應到圖中，就是先訪問當前頂點，再訪問與其鄰接的頂點；
• 中根遍歷是二叉樹這種特殊的樹形結構獨有的一種遍歷方式，因此我們不能夠通過該遍歷方式來拓展到圖的遍歷中；
• 后根遍歷的核心是：先訪問子樹，再訪問根結點，對應到圖中，就是先訪問與當前頂點鄰接的頂點，再訪問當前頂點；

不管是先根遍歷還是后根遍歷，其遍歷的方式都是沿著一條路徑先找到最深的結點，再去找其他結點。

對于先根遍歷與后根遍歷這種每次遍歷時都是沿著一條路徑，往深處走的方式進行遍歷，就是深度優先遍歷（Depth-First-Traversal, DFT）。

當我們要查找具體的對象時，采用這種沿著一條路徑，往深處走的方式進行查找，這就是深度優先搜索（Depth-First-Search, DFS）。

這里我們需要區分一下遍歷與搜索：

• 遍歷簡單的理解就是無條件地對數據結構中的所有元素進行訪問；
• 搜索簡單的理解就是有條件地對數據結構中的特定元素進行訪問；

由此可以看到，當所有元素都是搜索中的特定元素時，那么我們對存儲這些數據元素的數據結構進行搜索時，實際上就是在遍歷該數據結構。

因此我們可以簡單的理解為，遍歷與搜索的區別就是：對元素的訪問條件不同。

深度優先遍歷（DFT） 和 深度優先搜索（DFS） 是同一策略的不同應用場景，但術語上更常用 DFS 統稱。

這里一定要注意，在下面的介紹中，我們說的 DFS 實際上是說的對圖的遍歷算法，而不是查找特定值的算法。

理解了深度優先遍歷與深度優先搜索后，下面我們就來了解一下其算法思路；

二、算法思路

深度優先搜索的算法思路如下：

• 首先訪問圖中某一起始頂點 $v$
• 然后從 $v$ 出發，訪問與 $v$ 鄰接且未被訪問的任意一個頂點 $w_1$
• 再訪問與 $w_1$ 鄰接且未被訪問的人一個頂點 $w_2$
• 重復上述過程，直到 $w_i$ 不存在與其鄰接且未被訪問的頂點
• 當無法繼續訪問時，依次退回到最近被訪問的頂點
• 當退回后的頂點存在還未被訪問的鄰接頂點，則從該頂點繼續上述搜索過程，直至所有頂點完成訪問

這里我們以二叉樹的先序遍歷為例：

上圖中使用的是先根遍歷的方式進行展示：

• 二叉樹：先訪問根結點，再訪問子樹
• 圖：先訪問當前頂點，再訪問當前頂點的鄰接頂點

對于圖而言，其遍歷序列根據其存儲結構的不同而有所不同：

• 鄰接矩陣：同一起始頂點的遍歷序列相同
• 鄰接表：同一起始頂點的遍歷序列不同
• 十字鏈表：同一起始點的遍歷序列不同
• 鄰接多重表：同一起始點的遍歷序列不同

上圖所示的遍歷序列對于除鄰接矩陣外的存儲結構而言，只是其中的一種遍歷序列，僅供大家參考。

三、算法邏輯

今天我們要介紹的圖的深度優先搜索與樹的先根遍歷類似，都是先訪問當前頂點，再對一條路徑進行深入，直至該路徑無法繼續深入后，開始回溯，選擇下一條路徑進行深入；

在圖的 DFS 中我們需要對已經完成訪問的頂點進行標記，因此需要一個標記數組 visited[] 來記錄當前頂點是否被訪問。整個過程如下所示：

• 訪問當前起始頂點，并對起始頂點進行標記
• 通過 FirstNeighbor(G, x) 獲取當前頂點x的下一個鄰接頂點編號y，并通過 visited[y] 進行判斷該頂點是否被訪問：
  • visited[y] == false 則未被訪問，繼續對頂點y進行 DFS
  • visited[y] == true 則已被訪問，則說明該路徑上的頂點都已被訪問，接下來通過 NexttNeighbor(G, x, y) 獲取頂點x除了頂點y之外的下一個鄰接頂點編號z，并對該頂點進行判斷是否被訪問：
    • 存在未被訪問的頂點，繼續對該頂點進行 DFS
    • 不存在未被訪問的頂點，開始回溯

其代碼表達如下所示：

// 深度優先搜索
bool visited[MAXVERSIZE];
void DFS(graph* g, int x) {visit(g, x);					// 訪問當前頂點visited[x] = true;				// 標記當前頂點for (int y = FirstNeighbor(g, x); y >= 0; y = NextNeighbor(g, x, y)) {// FirstNeighbor(g, x): 當前頂點x存在下一個鄰接點，則返回對應頂點編號，否則，返回-1// NextNeighbor(g, x, y): 當前頂點x存在下一個除頂點y以外的鄰接點，則返回對應頂點編號，否則，返回-1// y == -1時，說明此時該路徑中不存在未被訪問的鄰接點if (!visited[y]) {			// 判斷當前頂點是否被訪問DFS(g, y);				// 未被訪問，則對該點進行深度優先搜索}}
}

對于連通圖而言，上述代碼邏輯足以完成所有頂點的遍歷，但是在非連通圖中，從某一起始點開始進行 DFS 只能完成該點所在連通分量的所有頂點的遍歷。

為了確保能夠對非連通圖完成所有頂點的遍歷，我們需要借助 visited[] 數組來查找未被訪問過的頂點信息，如下所示：

void DFSTraverse(graph* g) {// 初始化標記數組for (int i = 0; i < MAXVERSIZE; i++) {visited[i] = false;}for (int i = 0; i < MAXVERSIZE; i++) {if (!visited[i]) {DFS(g, i);}}
}

在該函數中，每一次調用 DFS 就是對圖中的一個連通分量進行遍歷，圖中存在多少個連通分量，就會調用多少次 DFS；

四、算法評價

圖的遍歷算法的本質就是通過邊來找頂點，因此對于 DFS 而言，其時間復雜度與 BFS 的時間復雜度一致：

• 鄰接矩陣：$O(|V{|}^2)$
• 鄰接表/十字鏈表/鄰接多重表：$O(|V|+|E|)$

在 DFS 中，我們可以像上述展示的代碼一樣，通過遞歸實現，其對應的空間復雜度為：$O(|V|)$

同樣也可以通過棧的方式來實現，對應的空間復雜度依然是：$O(|V|)$

五、深度優先生成樹

與廣度優先生成樹一致，深度優先生成樹也是在遍歷圖的過程中保留所有的頂點與其訪問的邊所得到的一棵生成樹，我們以下面的例子來說明：

在上圖中，其頂點集與邊集如下所示：

• 頂點集： V = { a , b , c , d , e , f , g } V = \{a, b, c, d, e, f, g\} V={a,b,c,d,e,f,g}
• 邊集：$E=\{(a,b),(a,c),(b,d),(b,e),(c,e),(e,f),(e,g),(f,g)\}$

當我們從起始點 a 開始進行遍歷時，此時點a 會被標記，其對應的生成樹為：

對于點a而言，其鄰接點有兩個：

• 點b：未訪問
• 點c：未訪問

當我們找到第一個鄰接點b時，點b會被標記，所對應的邊 $(a,b)$ 被訪問，對應的生成樹為：

對于點b而言，其鄰接點有3個：

• 點a：已訪問
• 點d：未訪問
• 點e：未訪問

這時找到的鄰接點a已經被訪問，算法會繼續尋找除了點a外的下一個鄰接點d。

當找到點d后，點d會被標記，所對應的邊 $(b,d)$ 被訪問，其對應的生成樹為：

對于點d而言，其鄰接點有1個：

• 點b：被訪問

由于點d不存在未被訪問的鄰接點，算法會開始回溯到點b，這時會繼續尋找與點b鄰接的下一個鄰接點e。

當找到點e后，點e會被標記，所對應的邊 $(b,e)$ 被訪問，對應的生成樹為：

對于點e而言，其鄰接點有4個：

• 點b：已訪問
• 點c：未訪問
• 點f：未訪問
• 點g：未訪問

這時算法會重復上述的步驟依次找到并標記以下頂點與邊：

• 頂點：c，對應邊：$(e,c)$
• 頂點：f，對應邊：$(e,f)$
• 頂點：g，對應邊：$(f,g)$

此時所有的頂點都完成了標記，我們也就得到了該圖的深度優先生成樹：

深度優先生成樹在不同的存儲結構中，同樣不相同：

• 鄰接矩陣：深度優先生成樹唯一
• 鄰接表/十字鏈表/鄰接多重表：深度優先生成樹不唯一

具體的原因我這里再重復一遍：

• 在鄰接表/十字鏈表/鄰接多重表中，邊的存儲是以鏈表的形式進行存儲，因此結點的位置可能發生變化，因此對應的生成樹也會發生變化

六、有向圖與無向圖

現在我們已經了解了圖的兩種遍歷方式：BFS 與 DFS ，不管是哪種方式，在對無向圖進行遍歷與對有向圖進行遍歷時，是有些許區別的：

• 在無向圖中，兩種遍歷方式的調用次數 = 連通分量的數量
• 在有向圖中，兩種遍歷方式的調用次數都需要根據實際情況進行分析：
  • 起始點到其它頂點都有路徑，則只需調用一次
  • 起始點與其它的頂點之間不存在路徑，則需多次調用
  • 有向圖為強連通圖，無論從哪個頂點出發，都只需要調用一次

在這兩個篇章中我們都是以無向圖為例進行說明，但是在實際問題中，我們還是需要根據具體情況進行具體分析。

結語：深潛與回溯，揭開圖論世界的另一面

通過本篇的探索，我們見證了深度優先搜索（DFS）如何以“不撞南墻不回頭”的執著，在圖結構中開辟出一條條縱深路徑。與廣度優先搜索（BFS）的“層層遞進”不同，DFS以遞歸與回溯為利器，在迷宮尋路、拓撲排序、連通分量統計等場景中展現獨特優勢。

關鍵回顧🔍

• DFS的核心邏輯：從二叉樹的遍歷（先序/后序）出發，推演至圖的深度探索策略，通過visited數組避免重復訪問，用遞歸或棧實現“一條路走到黑”的縱深突破。

• 生成樹的多樣性：DFS生成樹的形態因存儲結構（鄰接矩陣 vs 鄰接表）而異，揭示了算法執行路徑的不確定性，也體現了圖遍歷的靈活性。

• 場景適應性：

  • 無向圖：DFS調用次數=連通分量數，天然適合檢測圖的連通性。

  • 有向圖：強連通分量需特殊處理，DFS在依賴解析、環路檢測中表現卓越。

實踐啟示💡

• 代碼實現：遞歸簡潔但需警惕棧溢出，非遞歸棧實現更適合大規模圖。

• 性能權衡：鄰接表下DFS時間復雜度為$O(V+E)$，空間復雜度與遞歸深度正相關，樹形圖優化顯著。

• 決策智慧：遇到回溯問題、連通分量分析時優先考慮DFS；追求最短路徑或層序關系時轉向BFS。

如果本文對你有所啟發，歡迎互動支持！
👉 關注👆蒙奇D索大，獲取更多算法深度解析
👉 點贊👍鼓勵持續創作
👉 收藏📁備查實戰應用
👉 轉發📤分享給更多同行

圖論的海洋浩瀚無垠，DFS與BFS僅是探索的起點。下一篇我們將深入《圖的實際應用——最小生成樹（Minimum Spanning Tree）》，揭秘如何在復雜網絡中高效構建成本最低的連通骨架，無論是Kruskal的貪心策略，還是Prim的頂點擴展法，都將為你打開優化問題的新視野。敬請期待，一起用算法編織智慧之網！ 🌟