圖的深度優(yōu)先搜索指南一、深度優(yōu)先搜索（DFS）概述

深度優(yōu)先搜索（Depth-FirstSearch,DFS）是一種常用的圖遍歷算法，用于探索圖中的所有節(jié)點。該算法從起始節(jié)點出發(fā)，盡可能深入地探索每個分支，直到無法繼續(xù)前進，然后回溯到上一個節(jié)點，繼續(xù)探索其他未訪問的分支。DFS適用于無向圖和有向圖，常用于路徑尋找、連通性判斷、拓?fù)渑判虻葓鼍啊?/p>

（一）DFS的基本原理

1.訪問策略：優(yōu)先探索某個節(jié)點的鄰接節(jié)點，直到找到未訪問的節(jié)點，然后訪問該節(jié)點并繼續(xù)探索其鄰接節(jié)點。

2.回溯機制：當(dāng)某個節(jié)點的所有鄰接節(jié)點都已訪問或無法繼續(xù)探索時，算法回溯到上一個節(jié)點，繼續(xù)探索其他未訪問的鄰接節(jié)點。

3.終止條件：所有節(jié)點都被訪問或沒有可訪問的節(jié)點時，算法終止。

（二）DFS的實現(xiàn)方式

DFS可以通過遞歸或迭代的方式實現(xiàn)。遞歸方式簡潔直觀，而迭代方式通常使用棧來模擬遞歸過程。

二、DFS的具體實現(xiàn)

（一）遞歸實現(xiàn)

遞歸實現(xiàn)的DFS通過函數(shù)調(diào)用棧來管理節(jié)點的訪問順序。

1.初始化：創(chuàng)建一個訪問標(biāo)記數(shù)組，用于記錄每個節(jié)點是否已被訪問。

2.遞歸函數(shù)：

-訪問當(dāng)前節(jié)點，標(biāo)記為已訪問。

-遍歷當(dāng)前節(jié)點的所有鄰接節(jié)點，對未訪問的鄰接節(jié)點遞歸調(diào)用DFS函數(shù)。

示例代碼（偽代碼）：

DFS(node):

ifnodeisnotvisited:

marknodeasvisited

foreachneighborinnode'sneighbors:

DFS(neighbor)

（二）迭代實現(xiàn)

迭代實現(xiàn)的DFS使用棧來模擬遞歸過程。

1.初始化：創(chuàng)建一個訪問標(biāo)記數(shù)組和棧，將起始節(jié)點入棧并標(biāo)記為已訪問。

2.迭代過程：

-當(dāng)棧不為空時，彈出一個節(jié)點。

-遍歷該節(jié)點的所有鄰接節(jié)點，對未訪問的鄰接節(jié)點入棧并標(biāo)記為已訪問。

示例代碼（偽代碼）：

DFS_iterative(start_node):

stack=[]

visited=[Falsefor_inrange(num_nodes)]

stack.append(start_node)

visited[start_node]=True

whilestackisnotempty:

node=stack.pop()

process(node)

forneighborinnode'sneighbors:

ifnotvisited[neighbor]:

stack.append(neighbor)

visited[neighbor]=True

三、DFS的應(yīng)用場景

（一）路徑尋找

DFS可以用于尋找圖中的路徑，例如：

1.簡單路徑：從起始節(jié)點到目標(biāo)節(jié)點的任意路徑。

2.最短路徑：在無權(quán)圖中，DFS可以找到一條路徑，但不一定是最短的。

（二）連通性判斷

DFS可以判斷圖中是否存在連通分量：

1.無向圖：從任意節(jié)點出發(fā)，若能訪問到所有節(jié)點，則圖是連通的。

2.有向圖：若能從任意節(jié)點訪問到所有其他節(jié)點，則圖是強連通的。

（三）拓?fù)渑判?/p>

DFS可用于對有向無環(huán)圖（DAG）進行拓?fù)渑判颍?/p>

1.Kahn算法：基于入度數(shù)組，逐層輸出節(jié)點。

2.DFS算法：通過DFS訪問節(jié)點，按訪問結(jié)束時間排序。

四、DFS的優(yōu)缺點

（一）優(yōu)點

1.空間效率高：遞歸實現(xiàn)的DFS空間復(fù)雜度為O(h)，其中h為遞歸深度。迭代實現(xiàn)的DFS空間復(fù)雜度為O(V)，其中V為節(jié)點數(shù)。

2.實現(xiàn)簡單：遞歸實現(xiàn)的DFS代碼簡潔，易于理解。

3.適用于稀疏圖：在稀疏圖中，DFS的效率較高。

（二）缺點

1.可能陷入無限循環(huán)：在有向環(huán)圖中，若無適當(dāng)?shù)慕K止條件，DFS可能陷入無限循環(huán)。

2.最短路徑問題：DFS不保證找到最短路徑。

3.遍歷順序不固定：DFS的遍歷順序依賴于節(jié)點的鄰接順序，可能影響某些應(yīng)用場景。

五、總結(jié)

深度優(yōu)先搜索（DFS）是一種重要的圖遍歷算法，通過遞歸或迭代的方式實現(xiàn)。DFS適用于多種圖應(yīng)用場景，如路徑尋找、連通性判斷和拓?fù)渑判颉ｋm然DFS具有空間效率高、實現(xiàn)簡單等優(yōu)點，但也存在可能陷入無限循環(huán)、不保證最短路徑等缺點。在實際應(yīng)用中，需根據(jù)具體需求選擇合適的圖遍歷算法。

二、DFS的具體實現(xiàn)

（一）遞歸實現(xiàn)

遞歸實現(xiàn)的DFS利用程序調(diào)用棧來隱式管理節(jié)點的訪問順序。其核心思想是深入探索每個分支，直到達(dá)到葉子節(jié)點或已訪問節(jié)點，然后回溯到前一個節(jié)點繼續(xù)探索。

1.初始化階段：

創(chuàng)建一個與圖節(jié)點一一對應(yīng)的訪問標(biāo)記數(shù)組（例如`visited`），初始時所有節(jié)點標(biāo)記為`False`或`未訪問`，表示尚未探索。

選擇一個起始節(jié)點`start_node`，作為算法的入口點。

定義一個遞歸函數(shù)`DFS(node)`，該函數(shù)負(fù)責(zé)訪問節(jié)點`node`并遞歸訪問其未訪問的鄰接節(jié)點。

2.遞歸函數(shù)核心邏輯：

訪問當(dāng)前節(jié)點：

檢查當(dāng)前節(jié)點`node`是否已被訪問（`visited[node]`是否為`True`）。

如果`node`未被訪問，則執(zhí)行訪問操作（例如打印節(jié)點信息、記錄路徑等）。

將當(dāng)前節(jié)點標(biāo)記為已訪問（`visited[node]=True`）。

遞歸探索鄰接節(jié)點：

獲取當(dāng)前節(jié)點`node`的所有鄰接節(jié)點列表（`neighbors(node)`）。這一步取決于圖是使用鄰接矩陣還是鄰接表表示。

遍歷`node`的所有鄰接節(jié)點`neighbor`。

對于每個鄰接節(jié)點`neighbor`，判斷其是否已被訪問（`visited[neighbor]`是否為`False`）。

如果`neighbor`未被訪問，則對`neighbor`遞歸調(diào)用`DFS(neighbor)`，即`DFS(neighbor)`。這會繼續(xù)深入探索該分支。

注意：遍歷順序（例如先訪問左鄰接節(jié)點還是右鄰接節(jié)點）會影響最終結(jié)果，但通常不影響算法的基本邏輯。

3.觸發(fā)起始遞歸：

在主程序中，調(diào)用`DFS(start_node)`來啟動整個遍歷過程。

示例代碼（以鄰接表表示的無向圖為例，偽代碼）：

//初始化訪問標(biāo)記數(shù)組

visited=[Falsefor_inrange(num_nodes)]//num_nodes是節(jié)點總數(shù)

//定義遞歸DFS函數(shù)

DFS(node):

//1.訪問當(dāng)前節(jié)點

ifnotvisited[node]:

print("訪問節(jié)點:",node)//執(zhí)行實際訪問操作

marknodeasvisited//標(biāo)記為已訪問

//2.遞歸探索所有未訪問的鄰接節(jié)點

forneighboringet_neighbors(node)://get_neighbors(node)返回node的所有鄰接節(jié)點列表

ifnotvisited[neighbor]:

DFS(neighbor)//遞歸調(diào)用

//主程序入口

main():

start_node=0//假設(shè)從節(jié)點0開始

DFS(start_node)

遞歸實現(xiàn)的優(yōu)點：代碼簡潔，邏輯清晰，容易理解。符合人類探索時“深入挖掘”的思維模式。

遞歸實現(xiàn)的缺點：

棧溢出風(fēng)險：對于非常深的圖（即路徑很長），遞歸調(diào)用的深度可能超過系統(tǒng)棧的最大容量，導(dǎo)致棧溢出錯誤。

回溯自動管理：遞歸函數(shù)的自然特性使得回溯過程（即探索完一條路徑后返回到前一個節(jié)點）自動發(fā)生，無需手動管理。

（二）迭代實現(xiàn)

迭代實現(xiàn)的DFS使用顯式的數(shù)據(jù)結(jié)構(gòu)（通常是棧）來模擬遞歸調(diào)用棧的行為，手動管理節(jié)點的訪問和回溯。

1.初始化階段：

創(chuàng)建一個與圖節(jié)點一一對應(yīng)的訪問標(biāo)記數(shù)組（例如`visited`），初始時所有節(jié)點標(biāo)記為`False`或`未訪問`。

創(chuàng)建一個棧（例如`stack`），用于存儲接下來要訪問的節(jié)點。

選擇一個起始節(jié)點`start_node`。

將起始節(jié)點`start_node`入棧（`stack.push(start_node)`）。

將起始節(jié)點標(biāo)記為已訪問（`visited[start_node]=True`），因為即使入棧前也常先標(biāo)記。

2.迭代循環(huán)核心邏輯：

循環(huán)條件：當(dāng)棧`stack`不為空時，繼續(xù)執(zhí)行遍歷過程。

訪問當(dāng)前節(jié)點：

從棧中彈出一個節(jié)點`node`（`node=stack.pop()`）。

執(zhí)行對`node`的訪問操作（例如打印節(jié)點信息、記錄路徑等）。

探索鄰接節(jié)點：

獲取當(dāng)前節(jié)點`node`的所有鄰接節(jié)點列表（`get_neighbors(node)`）。

遍歷`node`的所有鄰接節(jié)點`neighbor`。

對于每個鄰接節(jié)點`neighbor`，判斷其是否已被訪問（`visited[neighbor]`是否為`False`）。

如果`neighbor`未被訪問：

將`neighbor`標(biāo)記為已訪問（`visited[neighbor]=True`）。

將`neighbor`入棧（`stack.push(neighbor)`）。這一步?jīng)Q定`neighbor`何時被訪問，通常選擇先入棧的鄰接節(jié)點先被訪問，遍歷順序與遞歸實現(xiàn)一致。

3.終止條件：

當(dāng)棧`stack`為空時，表示所有可達(dá)節(jié)點都已被訪問或標(biāo)記，迭代過程結(jié)束。

示例代碼（以鄰接表表示的無向圖為例，偽代碼）：

//初始化訪問標(biāo)記數(shù)組和棧

visited=[Falsefor_inrange(num_nodes)]

stack=[]

//定義獲取鄰接節(jié)點的函數(shù)

get_neighbors(node):

//返回節(jié)點node的所有未訪問鄰接節(jié)點列表

//示例：return[n1,n2,...]

pass

//主程序入口

main():

start_node=0//假設(shè)從節(jié)點0開始

stack.push(start_node)

visited[start_node]=True

whilestackisnotempty:

//1.從棧中彈出一個節(jié)點

node=stack.pop()

print("訪問節(jié)點:",node)//執(zhí)行實際訪問操作

//2.探索所有未訪問的鄰接節(jié)點

forneighboringet_neighbors(node):

ifnotvisited[neighbor]:

visited[neighbor]=True//標(biāo)記為已訪問

stack.push(neighbor)//入棧，稍后訪問

迭代實現(xiàn)的優(yōu)點：

避免棧溢出：顯式使用棧，不受系統(tǒng)調(diào)用棧深度的限制，適用于非常深的圖。

可控性更強：可以更容易地修改節(jié)點的入棧順序，或處理特殊的回溯邏輯。

迭代實現(xiàn)的缺點：

代碼相對復(fù)雜：相比遞歸實現(xiàn)，需要手動管理棧和訪問標(biāo)記，代碼略顯繁瑣。

顯式管理回溯：需要明確編寫代碼來處理回溯過程。

三、DFS的應(yīng)用場景

（一）路徑尋找

DFS可用于在圖中尋找從起始節(jié)點到目標(biāo)節(jié)點的路徑，盡管它不保證找到最短路徑，但能找到一條存在的路徑。

1.簡單路徑查找：

步驟：

執(zhí)行DFS遍歷，同時記錄訪問路徑（例如使用父節(jié)點指針數(shù)組`parent`或直接記錄節(jié)點序列`path`）。

在DFS訪問目標(biāo)節(jié)點`target`時，通過`parent`數(shù)組或`path`記錄回溯構(gòu)建完整路徑。

如果目標(biāo)節(jié)點可達(dá)，則返回從起始節(jié)點到目標(biāo)節(jié)點的路徑；否則，表示無路徑。

示例：在迷宮中尋找從入口到出口的任意一條通路。

2.所有簡單路徑查找：

步驟：

在DFS遞歸函數(shù)中，當(dāng)訪問到目標(biāo)節(jié)點時，不僅停止在該分支的進一步探索，還要將當(dāng)前路徑記錄下來。

使用一個列表（例如`all_paths`）來收集所有找到的路徑。

完成DFS遍歷后，返回`all_paths`列表。

應(yīng)用：在項目中查找所有符合特定條件的方法序列。

（二）連通性判斷

DFS是判斷圖中連通性的常用工具。

1.無向圖的連通性判斷：

步驟：

選擇任意一個起始節(jié)點`start`。

執(zhí)行DFS遍歷，從`start`開始。

遍歷結(jié)束后，檢查訪問標(biāo)記數(shù)組`visited`中有多少個元素被標(biāo)記為`True`。

如果所有節(jié)點都被標(biāo)記為`True`，則圖是連通的；否則，圖不連通。

應(yīng)用：判斷一個網(wǎng)絡(luò)中的所有主機是否在一個連通的網(wǎng)絡(luò)段中（不考慮實際網(wǎng)絡(luò)拓?fù)洌瑑H作算法示例）。

2.有向圖的強連通性判斷：

步驟：

方法一（基于單個DFS）：對有向圖執(zhí)行DFS，然后對生成的鄰接矩陣的轉(zhuǎn)置圖執(zhí)行DFS（即反向圖DFS），最后檢查反向DFS是否訪問了所有節(jié)點。如果訪問了所有節(jié)點，則圖是強連通的。該方法對算法理解有幫助，但不常用。

方法二（基于多個DFS）：執(zhí)行標(biāo)準(zhǔn)DFS，記錄所有節(jié)點的訪問結(jié)束時間（使用一個時間戳數(shù)組`finish_time`）。然后對所有節(jié)點按`finish_time`降序排序。最后，以排序后的節(jié)點順序執(zhí)行一次DFS。如果在這次DFS中能夠訪問到所有節(jié)點，則圖是強連通的。這是基于Kosaraju算法的核心思想。

應(yīng)用：在依賴關(guān)系圖中判斷是否存在循環(huán)依賴。

（三）拓?fù)渑判?/p>

拓?fù)渑判蚴且环N針對有向無環(huán)圖（DAG）的線性排序算法，輸出圖中所有節(jié)點的線性序列，使得對于每一條有向邊`(u,v)`，節(jié)點`u`在序列中出現(xiàn)在節(jié)點`v`之前。

1.基于DFS的拓?fù)渑判蛩惴ǎ↘ahn算法的變種思路）：

前提：確保輸入圖是無環(huán)的有向圖。

步驟：

初始化：

計算每個節(jié)點的出度（即有多少條有向邊以該節(jié)點為起點）。

創(chuàng)建一個隊列`queue`，將所有出度為0的節(jié)點（即沒有前驅(qū)的節(jié)點）入隊。

迭代過程：

當(dāng)`queue`不為空時：

從`queue`中彈出一個節(jié)點`u`。

將`u`加入拓?fù)渑判蚪Y(jié)果序列`topo_order`。

遍歷節(jié)點`u`的所有出邊（即所有以`u`為起點的邊`(u,v)`）：

獲取目標(biāo)節(jié)點`v`。

將節(jié)點`v`的出度減1。

如果節(jié)點`v`的出度變?yōu)?，則將`v`入隊。

終止與驗證：

如果`topo_order`的長度等于圖中節(jié)點總數(shù)`V`，則成功得到拓?fù)渑判?，返回`topo_order`。

如果`topo_order`的長度小于`V`，說明圖中存在環(huán)（因為環(huán)中的節(jié)點永遠(yuǎn)無法將出度減到0），因此無法進行拓?fù)渑判颉?/p>

2.基于DFS訪問結(jié)束時間的拓?fù)渑判颍?/p>

步驟：

初始化：創(chuàng)建訪問標(biāo)記數(shù)組`visited`，拓?fù)渑判蚪Y(jié)果列表`topo_order`，以及一個時間戳變量`time`。

執(zhí)行DFS：對每個節(jié)點`v`，如果`visited[v]`為`False`，則執(zhí)行DFS(v)，并在DFS(v)函數(shù)內(nèi)部管理訪問結(jié)束時間。

DFS(v)函數(shù)內(nèi)部：

標(biāo)記`v`為已訪問。

遍歷`v`的所有鄰接節(jié)點`u`：

如果`u`未被訪問，則遞歸調(diào)用DFS(u)。

在訪問完`v`的所有鄰接節(jié)點后，將時間戳`time`加1，并將`v`的訪問結(jié)束時間設(shè)置為`time`。

構(gòu)建拓?fù)湫蛄校涸贒FS結(jié)束后，根據(jù)每個節(jié)點的訪問結(jié)束時間，按結(jié)束時間降序排列節(jié)點，得到`topo_order`。

應(yīng)用：對課程依賴關(guān)系進行排序，確保在修讀某門課程前已修完其先修課程；任務(wù)調(diào)度優(yōu)化。

四、DFS的優(yōu)缺點

（一）優(yōu)點

1.空間效率相對較高（遞歸實現(xiàn)）：對于遞歸實現(xiàn)，空間復(fù)雜度主要取決于遞歸調(diào)用的最大深度，即圖的“高度”。在稀疏圖或平衡圖中，這個深度通常遠(yuǎn)小于節(jié)點總數(shù)V。相比之下，基于廣度優(yōu)先搜索（BFS）的算法通常需要O(V)的空間來存儲所有節(jié)點。然而，在極端情況下（如退化成鏈表的圖），DFS的遞歸深度可能接近O(V)，此時空間復(fù)雜度也接近O(V)。

2.空間效率絕對較高（迭代實現(xiàn)）：迭代實現(xiàn)的DFS明確使用一個棧來存儲待訪問節(jié)點，其空間復(fù)雜度恒定為O(V)，與圖的具體形狀無關(guān)。

3.代碼實現(xiàn)簡潔（遞歸實現(xiàn)）：遞歸方式天然地模擬了深入探索的過程，代碼通常更簡潔、易于編寫和理解。

4.適用于探索性任務(wù)：DFS的“深入挖掘”特性使其適合用于需要探索所有可能性或找到滿足特定深度條件的解的場景。

5.易于實現(xiàn)回溯：無論是遞歸還是迭代實現(xiàn)，DFS的回溯邏輯（探索完一條路后返回）都比較自然，易于編碼實現(xiàn)。

（二）缺點

1.可能找不到解或結(jié)果不最優(yōu)：

找不到解：如果目標(biāo)是尋找從起始點到目標(biāo)點的路徑，但圖中不存在這樣的路徑，DFS仍然會訪問所有可達(dá)節(jié)點后結(jié)束。

非最優(yōu)解：DFS不保證找到最短路徑或最少步數(shù)的路徑（除非圖是帶權(quán)重的，且每次都優(yōu)先選擇鄰接節(jié)點中“最優(yōu)”的那個，但這通常更接近貪婪算法）。

2.時間效率可能較低：在某些問題中，DFS可能會探索大量不必要的分支，尤其是在目標(biāo)節(jié)點位于圖深處或遠(yuǎn)離起始節(jié)點時。相比之下，BFS在尋找最短路徑時通常更有效率。

3.深度限制與棧溢出（遞歸實現(xiàn)）：如前所述，遞歸實現(xiàn)的DFS在處理非常深的圖時可能因調(diào)用棧溢出而失敗。

4.需要顯式管理訪問狀態(tài)（迭代實現(xiàn)）：迭代實現(xiàn)需要手動維護訪問標(biāo)記數(shù)組和顯式棧，相對遞歸實現(xiàn)而言，代碼稍顯復(fù)雜，且容易出錯。

5.無法保證訪問順序的普適性：DFS的遍歷順序依賴于節(jié)點鄰接關(guān)系的存儲順序（如鄰接表的順序）和鄰接節(jié)點的遍歷順序，這可能導(dǎo)致結(jié)果的不確定性或難以預(yù)測。

五、總結(jié)

深度優(yōu)先搜索（DFS）是一種基礎(chǔ)且強大的圖遍歷算法，通過遞歸或迭代的方式實現(xiàn)。它以“深入挖掘”的策略探索圖的分支，具有空間效率相對較高（尤其是迭代實現(xiàn)）、代碼簡潔（尤其是遞歸實現(xiàn)）等優(yōu)點。然而，DFS也存在可能找不到解、結(jié)果不最優(yōu)、在深圖中可能棧溢出（遞歸）、需要手動管理狀態(tài)（迭代）等缺點。

選擇DFS還是其他圖算法（如廣度優(yōu)先搜索BFS）取決于具體問題的需求：

當(dāng)需要找到一條存在的路徑（不要求最短）、判斷連通性、進行拓?fù)渑判?，或者圖的深度不是特別巨大時，DFS是一個很好的選擇。

當(dāng)需要尋找最短路徑（無權(quán)圖或帶權(quán)圖中使用BFS）、確保按特定順序訪問節(jié)點（如按層級），或者需要保證訪問所有節(jié)點時按層次展開時，BFS可能更合適。

理解DFS的工作原理和優(yōu)缺點，有助于在解決實際問題時選擇最合適的算法，并有效地實現(xiàn)和優(yōu)化。

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

深度優(yōu)先搜索（Depth-FirstSearch,DFS）是一種常用的圖遍歷算法，用于探索圖中的所有節(jié)點。該算法從起始節(jié)點出發(fā)，盡可能深入地探索每個分支，直到無法繼續(xù)前進，然后回溯到上一個節(jié)點，繼續(xù)探索其他未訪問的分支。DFS適用于無向圖和有向圖，常用于路徑尋找、連通性判斷、拓?fù)渑判虻葓鼍啊?/p>

（一）DFS的基本原理

1.訪問策略：優(yōu)先探索某個節(jié)點的鄰接節(jié)點，直到找到未訪問的節(jié)點，然后訪問該節(jié)點并繼續(xù)探索其鄰接節(jié)點。

2.回溯機制：當(dāng)某個節(jié)點的所有鄰接節(jié)點都已訪問或無法繼續(xù)探索時，算法回溯到上一個節(jié)點，繼續(xù)探索其他未訪問的鄰接節(jié)點。

3.終止條件：所有節(jié)點都被訪問或沒有可訪問的節(jié)點時，算法終止。

（二）DFS的實現(xiàn)方式

DFS可以通過遞歸或迭代的方式實現(xiàn)。遞歸方式簡潔直觀，而迭代方式通常使用棧來模擬遞歸過程。

二、DFS的具體實現(xiàn)

（一）遞歸實現(xiàn)

遞歸實現(xiàn)的DFS通過函數(shù)調(diào)用棧來管理節(jié)點的訪問順序。

1.初始化：創(chuàng)建一個訪問標(biāo)記數(shù)組，用于記錄每個節(jié)點是否已被訪問。

2.遞歸函數(shù)：

-訪問當(dāng)前節(jié)點，標(biāo)記為已訪問。

-遍歷當(dāng)前節(jié)點的所有鄰接節(jié)點，對未訪問的鄰接節(jié)點遞歸調(diào)用DFS函數(shù)。

示例代碼（偽代碼）：

DFS(node):

ifnodeisnotvisited:

marknodeasvisited

foreachneighborinnode'sneighbors:

DFS(neighbor)

（二）迭代實現(xiàn)

迭代實現(xiàn)的DFS使用棧來模擬遞歸過程。

1.初始化：創(chuàng)建一個訪問標(biāo)記數(shù)組和棧，將起始節(jié)點入棧并標(biāo)記為已訪問。

2.迭代過程：

-當(dāng)棧不為空時，彈出一個節(jié)點。

-遍歷該節(jié)點的所有鄰接節(jié)點，對未訪問的鄰接節(jié)點入棧并標(biāo)記為已訪問。

示例代碼（偽代碼）：

DFS_iterative(start_node):

stack=[]

visited=[Falsefor_inrange(num_nodes)]

stack.append(start_node)

visited[start_node]=True

whilestackisnotempty:

node=stack.pop()

process(node)

forneighborinnode'sneighbors:

ifnotvisited[neighbor]:

stack.append(neighbor)

visited[neighbor]=True

三、DFS的應(yīng)用場景

（一）路徑尋找

DFS可以用于尋找圖中的路徑，例如：

1.簡單路徑：從起始節(jié)點到目標(biāo)節(jié)點的任意路徑。

2.最短路徑：在無權(quán)圖中，DFS可以找到一條路徑，但不一定是最短的。

（二）連通性判斷

DFS可以判斷圖中是否存在連通分量：

1.無向圖：從任意節(jié)點出發(fā)，若能訪問到所有節(jié)點，則圖是連通的。

2.有向圖：若能從任意節(jié)點訪問到所有其他節(jié)點，則圖是強連通的。

（三）拓?fù)渑判?/p>

DFS可用于對有向無環(huán)圖（DAG）進行拓?fù)渑判颍?/p>

1.Kahn算法：基于入度數(shù)組，逐層輸出節(jié)點。

2.DFS算法：通過DFS訪問節(jié)點，按訪問結(jié)束時間排序。

四、DFS的優(yōu)缺點

（一）優(yōu)點

1.空間效率高：遞歸實現(xiàn)的DFS空間復(fù)雜度為O(h)，其中h為遞歸深度。迭代實現(xiàn)的DFS空間復(fù)雜度為O(V)，其中V為節(jié)點數(shù)。

2.實現(xiàn)簡單：遞歸實現(xiàn)的DFS代碼簡潔，易于理解。

3.適用于稀疏圖：在稀疏圖中，DFS的效率較高。

（二）缺點

1.可能陷入無限循環(huán)：在有向環(huán)圖中，若無適當(dāng)?shù)慕K止條件，DFS可能陷入無限循環(huán)。

2.最短路徑問題：DFS不保證找到最短路徑。

3.遍歷順序不固定：DFS的遍歷順序依賴于節(jié)點的鄰接順序，可能影響某些應(yīng)用場景。

五、總結(jié)

深度優(yōu)先搜索（DFS）是一種重要的圖遍歷算法，通過遞歸或迭代的方式實現(xiàn)。DFS適用于多種圖應(yīng)用場景，如路徑尋找、連通性判斷和拓?fù)渑判?。雖然DFS具有空間效率高、實現(xiàn)簡單等優(yōu)點，但也存在可能陷入無限循環(huán)、不保證最短路徑等缺點。在實際應(yīng)用中，需根據(jù)具體需求選擇合適的圖遍歷算法。

二、DFS的具體實現(xiàn)

（一）遞歸實現(xiàn)

遞歸實現(xiàn)的DFS利用程序調(diào)用棧來隱式管理節(jié)點的訪問順序。其核心思想是深入探索每個分支，直到達(dá)到葉子節(jié)點或已訪問節(jié)點，然后回溯到前一個節(jié)點繼續(xù)探索。

1.初始化階段：

創(chuàng)建一個與圖節(jié)點一一對應(yīng)的訪問標(biāo)記數(shù)組（例如`visited`），初始時所有節(jié)點標(biāo)記為`False`或`未訪問`，表示尚未探索。

選擇一個起始節(jié)點`start_node`，作為算法的入口點。

定義一個遞歸函數(shù)`DFS(node)`，該函數(shù)負(fù)責(zé)訪問節(jié)點`node`并遞歸訪問其未訪問的鄰接節(jié)點。

2.遞歸函數(shù)核心邏輯：

訪問當(dāng)前節(jié)點：

檢查當(dāng)前節(jié)點`node`是否已被訪問（`visited[node]`是否為`True`）。

如果`node`未被訪問，則執(zhí)行訪問操作（例如打印節(jié)點信息、記錄路徑等）。

將當(dāng)前節(jié)點標(biāo)記為已訪問（`visited[node]=True`）。

遞歸探索鄰接節(jié)點：

獲取當(dāng)前節(jié)點`node`的所有鄰接節(jié)點列表（`neighbors(node)`）。這一步取決于圖是使用鄰接矩陣還是鄰接表表示。

遍歷`node`的所有鄰接節(jié)點`neighbor`。

對于每個鄰接節(jié)點`neighbor`，判斷其是否已被訪問（`visited[neighbor]`是否為`False`）。

如果`neighbor`未被訪問，則對`neighbor`遞歸調(diào)用`DFS(neighbor)`，即`DFS(neighbor)`。這會繼續(xù)深入探索該分支。

注意：遍歷順序（例如先訪問左鄰接節(jié)點還是右鄰接節(jié)點）會影響最終結(jié)果，但通常不影響算法的基本邏輯。

3.觸發(fā)起始遞歸：

在主程序中，調(diào)用`DFS(start_node)`來啟動整個遍歷過程。

示例代碼（以鄰接表表示的無向圖為例，偽代碼）：

//初始化訪問標(biāo)記數(shù)組

visited=[Falsefor_inrange(num_nodes)]//num_nodes是節(jié)點總數(shù)

//定義遞歸DFS函數(shù)

DFS(node):

//1.訪問當(dāng)前節(jié)點

ifnotvisited[node]:

print("訪問節(jié)點:",node)//執(zhí)行實際訪問操作

marknodeasvisited//標(biāo)記為已訪問

//2.遞歸探索所有未訪問的鄰接節(jié)點

forneighboringet_neighbors(node)://get_neighbors(node)返回node的所有鄰接節(jié)點列表

ifnotvisited[neighbor]:

DFS(neighbor)//遞歸調(diào)用

//主程序入口

main():

start_node=0//假設(shè)從節(jié)點0開始

DFS(start_node)

遞歸實現(xiàn)的優(yōu)點：代碼簡潔，邏輯清晰，容易理解。符合人類探索時“深入挖掘”的思維模式。

遞歸實現(xiàn)的缺點：

棧溢出風(fēng)險：對于非常深的圖（即路徑很長），遞歸調(diào)用的深度可能超過系統(tǒng)棧的最大容量，導(dǎo)致棧溢出錯誤。

回溯自動管理：遞歸函數(shù)的自然特性使得回溯過程（即探索完一條路徑后返回到前一個節(jié)點）自動發(fā)生，無需手動管理。

（二）迭代實現(xiàn)

迭代實現(xiàn)的DFS使用顯式的數(shù)據(jù)結(jié)構(gòu)（通常是棧）來模擬遞歸調(diào)用棧的行為，手動管理節(jié)點的訪問和回溯。

1.初始化階段：

創(chuàng)建一個與圖節(jié)點一一對應(yīng)的訪問標(biāo)記數(shù)組（例如`visited`），初始時所有節(jié)點標(biāo)記為`False`或`未訪問`。

創(chuàng)建一個棧（例如`stack`），用于存儲接下來要訪問的節(jié)點。

選擇一個起始節(jié)點`start_node`。

將起始節(jié)點`start_node`入棧（`stack.push(start_node)`）。

將起始節(jié)點標(biāo)記為已訪問（`visited[start_node]=True`），因為即使入棧前也常先標(biāo)記。

2.迭代循環(huán)核心邏輯：

循環(huán)條件：當(dāng)棧`stack`不為空時，繼續(xù)執(zhí)行遍歷過程。

訪問當(dāng)前節(jié)點：

從棧中彈出一個節(jié)點`node`（`node=stack.pop()`）。

執(zhí)行對`node`的訪問操作（例如打印節(jié)點信息、記錄路徑等）。

探索鄰接節(jié)點：

獲取當(dāng)前節(jié)點`node`的所有鄰接節(jié)點列表（`get_neighbors(node)`）。

遍歷`node`的所有鄰接節(jié)點`neighbor`。

對于每個鄰接節(jié)點`neighbor`，判斷其是否已被訪問（`visited[neighbor]`是否為`False`）。

如果`neighbor`未被訪問：

將`neighbor`標(biāo)記為已訪問（`visited[neighbor]=True`）。

將`neighbor`入棧（`stack.push(neighbor)`）。這一步?jīng)Q定`neighbor`何時被訪問，通常選擇先入棧的鄰接節(jié)點先被訪問，遍歷順序與遞歸實現(xiàn)一致。

3.終止條件：

當(dāng)棧`stack`為空時，表示所有可達(dá)節(jié)點都已被訪問或標(biāo)記，迭代過程結(jié)束。

示例代碼（以鄰接表表示的無向圖為例，偽代碼）：

//初始化訪問標(biāo)記數(shù)組和棧

visited=[Falsefor_inrange(num_nodes)]

stack=[]

//定義獲取鄰接節(jié)點的函數(shù)

get_neighbors(node):

//返回節(jié)點node的所有未訪問鄰接節(jié)點列表

//示例：return[n1,n2,...]

pass

//主程序入口

main():

start_node=0//假設(shè)從節(jié)點0開始

stack.push(start_node)

visited[start_node]=True

whilestackisnotempty:

//1.從棧中彈出一個節(jié)點

node=stack.pop()

print("訪問節(jié)點:",node)//執(zhí)行實際訪問操作

//2.探索所有未訪問的鄰接節(jié)點

forneighboringet_neighbors(node):

ifnotvisited[neighbor]:

visited[neighbor]=True//標(biāo)記為已訪問

stack.push(neighbor)//入棧，稍后訪問

迭代實現(xiàn)的優(yōu)點：

避免棧溢出：顯式使用棧，不受系統(tǒng)調(diào)用棧深度的限制，適用于非常深的圖。

可控性更強：可以更容易地修改節(jié)點的入棧順序，或處理特殊的回溯邏輯。

迭代實現(xiàn)的缺點：

代碼相對復(fù)雜：相比遞歸實現(xiàn)，需要手動管理棧和訪問標(biāo)記，代碼略顯繁瑣。

顯式管理回溯：需要明確編寫代碼來處理回溯過程。

三、DFS的應(yīng)用場景

（一）路徑尋找

DFS可用于在圖中尋找從起始節(jié)點到目標(biāo)節(jié)點的路徑，盡管它不保證找到最短路徑，但能找到一條存在的路徑。

1.簡單路徑查找：

步驟：

執(zhí)行DFS遍歷，同時記錄訪問路徑（例如使用父節(jié)點指針數(shù)組`parent`或直接記錄節(jié)點序列`path`）。

在DFS訪問目標(biāo)節(jié)點`target`時，通過`parent`數(shù)組或`path`記錄回溯構(gòu)建完整路徑。

如果目標(biāo)節(jié)點可達(dá)，則返回從起始節(jié)點到目標(biāo)節(jié)點的路徑；否則，表示無路徑。

示例：在迷宮中尋找從入口到出口的任意一條通路。

2.所有簡單路徑查找：

步驟：

在DFS遞歸函數(shù)中，當(dāng)訪問到目標(biāo)節(jié)點時，不僅停止在該分支的進一步探索，還要將當(dāng)前路徑記錄下來。

使用一個列表（例如`all_paths`）來收集所有找到的路徑。

完成DFS遍歷后，返回`all_paths`列表。

應(yīng)用：在項目中查找所有符合特定條件的方法序列。

（二）連通性判斷

DFS是判斷圖中連通性的常用工具。

1.無向圖的連通性判斷：

步驟：

選擇任意一個起始節(jié)點`start`。

執(zhí)行DFS遍歷，從`start`開始。

遍歷結(jié)束后，檢查訪問標(biāo)記數(shù)組`visited`中有多少個元素被標(biāo)記為`True`。

如果所有節(jié)點都被標(biāo)記為`True`，則圖是連通的；否則，圖不連通。

應(yīng)用：判斷一個網(wǎng)絡(luò)中的所有主機是否在一個連通的網(wǎng)絡(luò)段中（不考慮實際網(wǎng)絡(luò)拓?fù)洌瑑H作算法示例）。

2.有向圖的強連通性判斷：

步驟：

方法一（基于單個DFS）：對有向圖執(zhí)行DFS，然后對生成的鄰接矩陣的轉(zhuǎn)置圖執(zhí)行DFS（即反向圖DFS），最后檢查反向DFS是否訪問了所有節(jié)點。如果訪問了所有節(jié)點，則圖是強連通的。該方法對算法理解有幫助，但不常用。

方法二（基于多個DFS）：執(zhí)行標(biāo)準(zhǔn)DFS，記錄所有節(jié)點的訪問結(jié)束時間（使用一個時間戳數(shù)組`finish_time`）。然后對所有節(jié)點按`finish_time`降序排序。最后，以排序后的節(jié)點順序執(zhí)行一次DFS。如果在這次DFS中能夠訪問到所有節(jié)點，則圖是強連通的。這是基于Kosaraju算法的核心思想。

應(yīng)用：在依賴關(guān)系圖中判斷是否存在循環(huán)依賴。

（三）拓?fù)渑判?/p>

拓?fù)渑判蚴且环N針對有向無環(huán)圖（DAG）的線性排序算法，輸出圖中所有節(jié)點的線性序列，使得對于每一條有向邊`(u,v)`，節(jié)點`u`在序列中出現(xiàn)在節(jié)點`v`之前。

1.基于DFS的拓?fù)渑判蛩惴ǎ↘ahn算法的變種思路）：

前提：確保輸入圖是無環(huán)的有向圖。

步驟：

初始化：

計算每個節(jié)點的出度（即有多少條有向邊以該節(jié)點為起點）。

創(chuàng)建一個隊列`queue`，將所有出度為0的節(jié)點（即沒有前驅(qū)的節(jié)點）入隊。

迭代過程：

當(dāng)`queue`不為空時：

從`queue`中彈出一個節(jié)點`u`。

將`u`加入拓?fù)渑判蚪Y(jié)果序列`topo_order`。

遍歷節(jié)點`u`的所有出邊（即所有以`u`為起點的邊`(u,v)`）：

獲取目標(biāo)節(jié)點`v`。

將節(jié)點`v`的出度減1。

如果節(jié)點`v`的出度變?yōu)?，則將`v`入隊。

終止與驗證：

如果`topo_order`的長度等于圖中節(jié)點總數(shù)`V`，則成功得到拓?fù)渑判?，返回`topo_order`。

如果`topo_order`的長度小于`V`，說明圖中存在環(huán)（因為環(huán)中的節(jié)點永遠(yuǎn)無法將出度減到0），因此無法進行拓?fù)渑判颉?/p>

2.基于DFS訪問結(jié)束時間的拓?fù)渑判颍?/p>

步驟：

初始化：創(chuàng)建訪問標(biāo)記數(shù)組`visited`，拓?fù)渑判蚪Y(jié)果列表`topo_order