深度優先搜尋簡介

深度優先搜尋是用於遍歷或搜尋樹或圖資料結構的演算法。一個從根開始,並在回溯之前儘可能地沿著每個分支進行探索。19 世紀法國數學家查爾斯·皮埃爾·特雷馬斯(CharlesPierreTrémaux)研究了一種深度優先搜尋作為解決迷宮的策略。

深度優先搜尋是查詢從源頂點可到達的所有頂點的系統方法。與廣度優先搜尋一樣,DFS 遍歷給定圖的連通元件並定義生成樹。深度優先搜尋的基本思想是有條不紊地探索每個邊緣。我們從必要的頂點開始。一旦我們發現了一個頂點,DFS 就會從它開始探索(不像 BFS,它將一個頂點放在一個佇列中以便以後從中進行探索)。

我們來看一個例子。我們將遍歷此圖:

StackOverflow 文件

我們將遵循以下規則遍歷圖表:

  • 我們將從源頭開始。
  • 沒有節點將被訪問兩次。
  • 我們尚未訪問的節點將是白色的。
  • 我們訪問過但未訪問其所有子節點的節點將顯示為灰色。
  • 完全遍歷的節點將變為黑色。

讓我們一步一步地看一下: StackOverflow 文件 StackOverflow 文件 StackOverflow 文件 StackOverflow 文件 StackOverflow 文件 StackOverflow 文件

我們可以看到一個重要的關鍵字這是後來的。你可以看到。 5-1 稱為後備。這是因為我們還沒有完成 node-1 ,所以從另一個節點到 node-1 意味著圖中有一個迴圈。在 DFS 中,如果我們可以從一個灰色節點轉到另一個灰色節點,我們可以確定圖形具有迴圈。這是在圖中檢測迴圈的方法之一。根據節點和我們訪問的節點的順序,我們可以找出一個迴圈中的任何邊緣作為後備。例如:如果我們從 1 開始到 5 ,我們就會發現 2-1 作為後備。 **** ****

我們從灰色節點到白色節點的邊緣稱為樹邊緣。如果我們只保留樹邊緣並刪除其他邊緣,我們將得到 DFS 樹

在無向圖中,如果我們可以訪問已訪問過的節點,那麼它必須是一個備份節點。但對於有向圖,我們必須檢查顏色。當且僅當我們可以從一個灰色節點轉到另一個灰色節點時,稱為後備

在 DFS 中,我們還可以為每個節點保留時間戳,這可以以多種方式使用(例如:拓撲排序)。

  1. 當節點 v 從白色變為灰色時,時間記錄在 d [v]中
  2. 當節點 v 從灰色變為黑色時,時間記錄在 f [v]中

這裡 d [] 表示發現時間f [] 表示結束時間。我們的 pesudo 程式碼看起來像:

Procedure DFS(G):
for each node u in V[G]
    color[u] := white
    parent[u] := NULL
end for
time := 0
for each node u in V[G]
    if color[u] == white
        DFS-Visit(u)
    end if
end for

Procedure DFS-Visit(u):
color[u] := gray
time := time + 1
d[u] := time
for each node v adjacent to u
    if color[v] == white
        parent[v] := u
        DFS-Visit(v)
    end if
end for
color[u] := black
time := time + 1
f[u] := time

複雜:

每個節點和邊都被訪問一次。因此 DFS 的複雜度為 O(V + E) ,其中 V 表示節點數, E 表示邊數。

深度優先搜尋的應用:

  • 在無向圖中查詢所有對最短路徑。
  • 在圖中檢測迴圈。
  • 尋找路徑。
  • 拓撲排序。
  • 測試圖表是否為二分圖。
  • 尋找強連線元件。
  • 用一種解決方案解決難題。