數據結構中的 DFS（深度優先遍歷）：什麼是、排序和應用

DFS在數據結構中的意義

數據結構中的 DFS，也稱為深度優先遍歷，是一種遞歸算法，主要用於搜索圖或樹數據結構的所有頂點。 遍歷是對圖的每個節點的訪問。 該算法從根節點（可能是圖中的根節點的任意節點）開始，並在回溯之前沿著每個分支盡可能遠。

這個想法是從根節點或任意節點開始並保持節點標記。 在此之後，您需要移動到未標記的相鄰節點並繼續此循環，直到沒有未標記的相鄰節點。 然後回溯並檢查未標記的其他節點並遍歷它們。 最後一步是打印路徑中的節點。

算法

制定一個遞歸函數，它將獲取節點的索引和訪問過的數組。

1. 保持當前節點標記為已訪問，然後打印它。
2. 遍歷所有相鄰的音符和未標記的音符，並使用相鄰節點的索引調用遞歸函數。

探索我們流行的軟件工程課程

特性

數據結構中 DFS 中的時間和空間分析根據其應用領域的不同而有所不同。 理論上，DFS主要用於穿越全圖，耗時O(|V|+|E|) 其中|V| 描述頂點數和|E| 描述了邊的數量。 該圖是線性的。

在這些應用程序中，空間 O(|V|) 也被用作最後的手段，以保留存儲在搜索路徑上的頂點堆棧和已訪問的頂點集。 因此，時間和空間界限的設置類似於廣度優先搜索。 在這裡，使用的兩種算法較少依賴於它們的複雜性，而更多地依賴於兩種算法產生的頂點順序的各種特徵。

當涉及到 DFS 在與特定領域相關的數據結構中的應用時，例如在網絡爬蟲或 AI 中尋找解決方案時，需要遍歷的圖可能太大而無法全部訪問。 在這種情況下，搜索只執行到有限的深度； 由於有限的資源，如磁盤空間或內存。 數據結構通常不用於跟踪之前訪問過的所有頂點的集合。 當涉及到擴展邊和頂點的單位時，執行到有限深度的搜索仍然使時間線性化。

但是，請記住，此數字與整個圖的大小不同，因為某些頂點可能會被搜索多次，而另一些則不會被搜索。

在這種情況下，DFS 還轉向啟發式方法來選擇更有希望的分支。 最後，當無法確定適當的深度限制時，通過一系列增長限制重複應用先驗的、迭代的加深 DFS。

從世界頂級大學在線學習軟件開發課程。 獲得行政 PG 課程、高級證書課程或碩士課程，以加快您的職業生涯。

深度優先搜索算法

標準 DFS 實現中圖的每個頂點都分為兩類：

1. 未訪問
2. 參觀過

該算法用於精確定位每個頂點並將它們標記為已訪問，同時避免循環。

這是 DFS 算法的工作原理：

1. 將圖的任何特定頂點放在堆棧上。
2. 堆棧頂部的項目應添加到訪問列表中。
3. 製作該頂點的相鄰節點列表，並將那些不在訪問列表中的節點添加到堆棧頂部。
4. 繼續重複前面的步驟，直到堆棧清空。

DFS 排序

頂點排序：在 DFS 中有四種方法可以對圖或樹的頂點進行線性排序：

1. DFS 算法首先訪問的頂點列表被稱為預排序。 這是描述搜索進度的簡潔方式。
2. 按算法最後訪問的順序排列的頂點列表稱為後排序。
3. 與第一次訪問順序相反的頂點列表是反向預排序。 因此，不應將其誤認為是後訂購。
4. 與上次訪問順序相反的頂點列表是反向後排序。 不應將其誤認為是預購。

此外，二叉樹還存在有序和逆序。

圖的深度優先搜索或 DFS

圖的 DFS 與樹的 DFS 幾乎相同。 唯一的區別是圖可能有循環，不像樹。 一個節點可能會被訪問多次，為了避免處理該節點，使用了一個布爾訪問數組。

深度優先搜索的輸出

深度優先搜索更容易用搜索中已經到達的頂點的生成樹來描述。 基於此生成樹，原始圖邊分為三類：樹的節點指向其後代之一的前向邊、節點指向其祖先之一的後向邊和交叉邊，它不執行前面的任何功能。

深度優先遍歷 (DFS) 的應用

深度優先搜索在以下算法中用作構建塊：

• 搜索已連接的組件。
• 查找 2-（頂點或邊）連接的組件。
• 尋找圖表的橋樑。
• 查找 3（頂點或邊）連接的組件。
• 拓撲排序。
• 查找強連接的組件。
• 找出一個物種是否與系統發育樹中的一個或另一個物種相似。
• 平面度測試。
• 產生詞來確定任何組的極限集。
• 解決只有一種解決方案的謎題，例如迷宮。
• 迷宮一代。
• 在圖中搜索雙連通性。

DFS 偽代碼和 Python 實現

init() 函數在下面偽代碼中的每個節點上運行，以確保訪問所有頂點。 這一點尤其重要，因為圖表可能有各種不連貫的區域。

這是偽代碼：

DFS(G, u)

u.visited = true

對於每個 v ∈ G.Adj[u]

如果 v.visited == false

DFS(G,v)

在裡面（） {

對於每個 u ∈ G

u.visited = 假

對於每個 u ∈ G

DFS(G, u)

}

這是 Python 中的 DFS 實現：

圖 = {

'5' : ['3','7'],

'2' : ['1', '3'],

'6' : ['7'],

'3' : [],

'4' : ['6'],

“7”：[]

}

訪問=設置（）

def dfs（已訪問，圖形，節點）：

如果節點未訪問：

打印（節點）

訪問過的.add（節點）

對於圖[節點]中的鄰居：

dfs（已訪問、圖表、鄰居）

print(“這是 DFS:”)

dfs（已訪問，圖表，'5'）

輸出：

這是 DFS：5

探索我們流行的軟件工程課程

深度優先搜索的複雜性

John Reif 探索了深度優先搜索的計算複雜性。 準確地說，在一個圖中，給定的事實是 G，讓 O 是由重複 DFS 算法確定的標準階。 G代表圖，O代表冗餘DFS算法的排序輸出。 此輸出稱為詞典 DFS 排序。

結論

DFS 算法的主要目標是訪問避免目標圖中循環的每個頂點。 如果您希望參與搜索操作或排序操作的高級實現，您絕對應該考慮學習深度優先搜索和數據結構的高級和整體課程。

upGrad有一些頂級的 DFS 課程，如計算機科學碩士和大數據專業。

如果您正在努力邁出下一步並尋求專家建議， upGrad Mentorship旨在為您提供與業內最佳職業顧問和專家的一對一課程。