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

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

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

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

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

• 時(shí)間復(fù)雜度：采用鄰接表存儲(chǔ)時(shí)為O(|V|+|E|)（|E|為邊數(shù)）；采用鄰接矩陣則為O(|V|2)，因?yàn)樾枰闅v整個(gè)矩陣來(lái)尋找鄰接點(diǎn)。

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

1. 典型應(yīng)用：拓?fù)渑判?、尋找連通分量、檢測(cè)圖中是否存在環(huán)、求解迷宮問(wèn)題、尋找圖的關(guān)節(jié)點(diǎn)等。

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

廣度優(yōu)先搜索遵循“層層推進(jìn)”的策略，類(lèi)似于樹(shù)的層序遍歷。

1. 核心思想：從起始頂點(diǎn)出發(fā)，首先訪問(wèn)其所有鄰接點(diǎn)，然后再按訪問(wèn)順序，依次訪問(wèn)這些鄰接點(diǎn)的未被訪問(wèn)的鄰接點(diǎn)，以此類(lèi)推，直到所有可達(dá)頂點(diǎn)都被訪問(wèn)。
2. 實(shí)現(xiàn)方式：必須借助隊(duì)列來(lái)管理待訪問(wèn)的頂點(diǎn)，確?！跋缺话l(fā)現(xiàn)的頂點(diǎn)先被訪問(wèn)”。
3. 算法特點(diǎn)：

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

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

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

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

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

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

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

1. 鄰接矩陣

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

• 遍歷支持分析：

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

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

1. 鄰接表

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

• 遍歷支持分析：

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

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

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

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

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

四、與對(duì)比

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

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