圖作為一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，廣泛應(yīng)用于社交網(wǎng)絡(luò)、路徑規(guī)劃、網(wǎng)絡(luò)拓撲等領(lǐng)域。圖的遍歷是圖算法的基礎(chǔ)，其中深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）是兩種最經(jīng)典且核心的遍歷策略。高效的遍歷離不開底層數(shù)據(jù)結(jié)構(gòu)的支持，即圖的存儲表示。本文將系統(tǒng)闡述DFS與BFS的原理、特點、應(yīng)用場景，并深入探討為其提供支持的幾種關(guān)鍵存儲服務(wù)（鄰接矩陣、鄰接表等），分析不同存儲方式對遍歷性能的影響。

一、深度優(yōu)先搜索（DFS）

深度優(yōu)先搜索遵循“一條路走到黑，再回溯”的策略。其過程類似于樹的先序遍歷。

1. 核心思想：從起始頂點出發(fā)，沿著某條路徑盡可能深地探索，直到該路徑上所有頂點均被訪問，然后回溯到上一個頂點，探索其未訪問的其他鄰接點，如此反復(fù)，直至圖中所有從起始點可達的頂點都被訪問。
2. 實現(xiàn)方式：通常借助棧（遞歸調(diào)用棧或顯式棧）來實現(xiàn)回溯功能。遞歸實現(xiàn)代碼簡潔，體現(xiàn)了DFS天然的遞歸結(jié)構(gòu)。
3. 算法特點：

• 空間復(fù)雜度：在最壞情況下（如圖呈線性鏈狀），遞歸深度為O(|V|)，其中|V|為頂點數(shù)。

• 時間復(fù)雜度：采用鄰接表存儲時為O(|V|+|E|)（|E|為邊數(shù)）；采用鄰接矩陣則為O(|V|2)，因為需要遍歷整個矩陣來尋找鄰接點。

• 生成樹/林：DFS遍歷過程中經(jīng)過的邊會形成一棵深度優(yōu)先樹（連通圖）或多棵深度優(yōu)先樹組成的深度優(yōu)先森林。

1. 典型應(yīng)用：拓撲排序、尋找連通分量、檢測圖中是否存在環(huán)、求解迷宮問題、尋找圖的關(guān)節(jié)點等。

二、廣度優(yōu)先搜索（BFS）

廣度優(yōu)先搜索遵循“層層推進”的策略，類似于樹的層序遍歷。

1. 核心思想：從起始頂點出發(fā)，首先訪問其所有鄰接點，然后再按訪問順序，依次訪問這些鄰接點的未被訪問的鄰接點，以此類推，直到所有可達頂點都被訪問。
2. 實現(xiàn)方式：必須借助隊列來管理待訪問的頂點，確保“先被發(fā)現(xiàn)的頂點先被訪問”。
3. 算法特點：

• 空間復(fù)雜度：在最壞情況下需要存儲一整層的頂點，對于稠密圖可能達到O(|V|)。

• 時間復(fù)雜度：與DFS相同，鄰接表為O(|V|+|E|)，鄰接矩陣為O(|V|2)。

• 最短路徑：在無權(quán)圖中，BFS從源點出發(fā)首次訪問到某個頂點的路徑，就是該頂點到源點的最短路徑。這是BFS一個極其重要的性質(zhì)。

• 生成樹：BFS遍歷過程形成的是廣度優(yōu)先樹。

1. 典型應(yīng)用：求解無權(quán)圖的最短路徑問題、社交網(wǎng)絡(luò)中查找“N度好友”、網(wǎng)絡(luò)廣播、GPS導(dǎo)航尋找最少換乘路線等。

三、圖的存儲支持服務(wù)

遍歷算法的效率與圖的具體存儲結(jié)構(gòu)（即“存儲支持服務(wù)”）緊密相關(guān)。主要存儲方式有：

1. 鄰接矩陣

• 表示方法：使用一個|V|×|V|的二維數(shù)組。對于無權(quán)圖，matrix[i][j] = 1表示頂點i到j(luò)有邊，為0則表示無邊。對于帶權(quán)圖，可存儲權(quán)值。

• 遍歷支持分析：

• 優(yōu)點：判斷任意兩個頂點間是否存在邊（即查詢操作）非常快，時間復(fù)雜度為O(1)。

• 缺點：空間開銷大，為O(|V|2)，對于稀疏圖浪費嚴(yán)重。在遍歷時（尤其是BFS/DFS尋找某個頂點的所有鄰接點），需要掃描一整行，導(dǎo)致在稀疏圖上的遍歷效率較低。

1. 鄰接表

• 表示方法：為每個頂點維護一個鏈表（或動態(tài)數(shù)組），鏈表中存儲與該頂點直接相鄰的所有頂點（對于帶權(quán)圖，可同時存儲權(quán)值）。

• 遍歷支持分析：

• 優(yōu)點：空間復(fù)雜度為O(|V|+|E|)，能高效利用稀疏圖的存儲空間。在遍歷時，能直接獲取一個頂點的所有鄰接點，無需掃描無效信息，這使得基于鄰接表的DFS/BFS時間復(fù)雜度優(yōu)化至O(|V|+|E|)。

• 缺點：判斷任意兩個頂點間是否有邊，需要遍歷其中一個頂點的鏈表，效率為O(度(vertex))，不如鄰接矩陣。

1. 其他存儲結(jié)構(gòu)

• 十字鏈表：針對有向圖的優(yōu)化存儲，結(jié)合了鄰接表和逆鄰接表，方便同時求取頂點的出邊和入邊。

• 鄰接多重表：針對無向圖的優(yōu)化存儲，一條邊只用一個結(jié)點表示，避免了鄰接表中邊被存儲兩次的問題，適用于需要頻繁操作邊的場景。

四、與對比

| 特性 | 深度優(yōu)先搜索 (DFS) | 廣度優(yōu)先搜索 (BFS) |
| :--- | :--- | :--- |
| 數(shù)據(jù)結(jié)構(gòu) | 棧 (遞歸/顯式) | 隊列 |
| 遍歷順序 | 深度優(yōu)先，縱向延伸 | 廣度優(yōu)先，橫向擴展 |
| 解的性質(zhì) | 不保證最短路徑 | 保證無權(quán)圖最短路徑 |
| 空間消耗 | 與遞歸深度相關(guān)，通常較小 | 與每層寬度相關(guān)，可能較大 |
| 存儲服務(wù)影響 | 鄰接表效率遠高于鄰接矩陣 | 鄰接表效率遠高于鄰接矩陣 |

結(jié)論：DFS和BFS是圖遍歷的兩大支柱算法，選擇取決于問題本身（如求最短路徑必用BFS）。而鄰接表因其在稀疏圖中的空間高效性和遍歷時的直接性，成為實現(xiàn)這兩種算法最常用、最推薦的“存儲支持服務(wù)”。在實際系統(tǒng)（如社交網(wǎng)絡(luò)后端、推薦引擎）中，圖的存儲服務(wù)可能更為復(fù)雜，涉及分布式存儲、圖數(shù)據(jù)庫等，但其核心優(yōu)化思想依然圍繞著如何高效地支持“查找某個頂點的所有鄰居”這一遍歷基本操作展開。理解基礎(chǔ)存儲結(jié)構(gòu)與遍歷算法的關(guān)系，是設(shè)計和優(yōu)化更高級圖處理系統(tǒng)的重要基石。