圖作為一種重要的非線性數據結構，廣泛應用于社交網絡、路徑規劃、網絡拓撲等領域。圖的遍歷是圖算法的基礎，其中深度優先搜索（DFS）和廣度優先搜索（BFS）是兩種最經典且核心的遍歷策略。高效的遍歷離不開底層數據結構的支持，即圖的存儲表示。本文將系統闡述DFS與BFS的原理、特點、應用場景，并深入探討為其提供支持的幾種關鍵存儲服務（鄰接矩陣、鄰接表等），分析不同存儲方式對遍歷性能的影響。
一、深度優先搜索（DFS）
深度優先搜索遵循“一條路走到黑，再回溯”的策略。其過程類似于樹的先序遍歷。
- 核心思想：從起始頂點出發，沿著某條路徑盡可能深地探索，直到該路徑上所有頂點均被訪問，然后回溯到上一個頂點，探索其未訪問的其他鄰接點，如此反復，直至圖中所有從起始點可達的頂點都被訪問。
- 實現方式：通常借助棧（遞歸調用棧或顯式棧）來實現回溯功能。遞歸實現代碼簡潔，體現了DFS天然的遞歸結構。
- 算法特點：
- 空間復雜度：在最壞情況下（如圖呈線性鏈狀），遞歸深度為O(|V|)，其中|V|為頂點數。
- 時間復雜度：采用鄰接表存儲時為O(|V|+|E|)（|E|為邊數）；采用鄰接矩陣則為O(|V|2)，因為需要遍歷整個矩陣來尋找鄰接點。
- 生成樹/林：DFS遍歷過程中經過的邊會形成一棵深度優先樹（連通圖）或多棵深度優先樹組成的深度優先森林。
- 典型應用：拓撲排序、尋找連通分量、檢測圖中是否存在環、求解迷宮問題、尋找圖的關節點等。
二、廣度優先搜索（BFS）
廣度優先搜索遵循“層層推進”的策略，類似于樹的層序遍歷。
- 核心思想：從起始頂點出發，首先訪問其所有鄰接點，然后再按訪問順序，依次訪問這些鄰接點的未被訪問的鄰接點，以此類推，直到所有可達頂點都被訪問。
- 實現方式：必須借助隊列來管理待訪問的頂點，確保“先被發現的頂點先被訪問”。
- 算法特點：
- 空間復雜度：在最壞情況下需要存儲一整層的頂點，對于稠密圖可能達到O(|V|)。
- 時間復雜度：與DFS相同，鄰接表為O(|V|+|E|)，鄰接矩陣為O(|V|2)。
- 最短路徑：在無權圖中，BFS從源點出發首次訪問到某個頂點的路徑，就是該頂點到源點的最短路徑。這是BFS一個極其重要的性質。
- 生成樹：BFS遍歷過程形成的是廣度優先樹。
- 典型應用：求解無權圖的最短路徑問題、社交網絡中查找“N度好友”、網絡廣播、GPS導航尋找最少換乘路線等。
三、圖的存儲支持服務
遍歷算法的效率與圖的具體存儲結構（即“存儲支持服務”）緊密相關。主要存儲方式有：
- 鄰接矩陣
- 表示方法：使用一個|V|×|V|的二維數組。對于無權圖，
matrix[i][j] = 1表示頂點i到j有邊，為0則表示無邊。對于帶權圖，可存儲權值。
- 遍歷支持分析：
- 優點：判斷任意兩個頂點間是否存在邊（即查詢操作）非常快，時間復雜度為O(1)。
- 缺點：空間開銷大，為O(|V|2)，對于稀疏圖浪費嚴重。在遍歷時（尤其是BFS/DFS尋找某個頂點的所有鄰接點），需要掃描一整行，導致在稀疏圖上的遍歷效率較低。
- 鄰接表
- 表示方法：為每個頂點維護一個鏈表（或動態數組），鏈表中存儲與該頂點直接相鄰的所有頂點（對于帶權圖，可同時存儲權值）。
- 遍歷支持分析：
- 優點：空間復雜度為O(|V|+|E|)，能高效利用稀疏圖的存儲空間。在遍歷時，能直接獲取一個頂點的所有鄰接點，無需掃描無效信息，這使得基于鄰接表的DFS/BFS時間復雜度優化至O(|V|+|E|)。
- 缺點：判斷任意兩個頂點間是否有邊，需要遍歷其中一個頂點的鏈表，效率為O(度(vertex))，不如鄰接矩陣。
- 其他存儲結構
- 十字鏈表：針對有向圖的優化存儲，結合了鄰接表和逆鄰接表，方便同時求取頂點的出邊和入邊。
- 鄰接多重表：針對無向圖的優化存儲，一條邊只用一個結點表示，避免了鄰接表中邊被存儲兩次的問題，適用于需要頻繁操作邊的場景。
四、與對比
| 特性 | 深度優先搜索 (DFS) | 廣度優先搜索 (BFS) |
| :--- | :--- | :--- |
| 數據結構 | 棧 (遞歸/顯式) | 隊列 |
| 遍歷順序 | 深度優先，縱向延伸 | 廣度優先，橫向擴展 |
| 解的性質 | 不保證最短路徑 | 保證無權圖最短路徑 |
| 空間消耗 | 與遞歸深度相關，通常較小 | 與每層寬度相關，可能較大 |
| 存儲服務影響 | 鄰接表效率遠高于鄰接矩陣 | 鄰接表效率遠高于鄰接矩陣 |
結論：DFS和BFS是圖遍歷的兩大支柱算法，選擇取決于問題本身（如求最短路徑必用BFS）。而鄰接表因其在稀疏圖中的空間高效性和遍歷時的直接性，成為實現這兩種算法最常用、最推薦的“存儲支持服務”。在實際系統（如社交網絡后端、推薦引擎）中，圖的存儲服務可能更為復雜，涉及分布式存儲、圖數據庫等，但其核心優化思想依然圍繞著如何高效地支持“查找某個頂點的所有鄰居”這一遍歷基本操作展開。理解基礎存儲結構與遍歷算法的關系，是設計和優化更高級圖處理系統的重要基石。
