深度優先搜尋簡介

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

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

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

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

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

讓我們一步一步地看一下：

我們可以看到一個重要的關鍵字這是後來的。你可以看到。 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 表示邊數。

深度優先搜尋的應用：

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