資料結構中圖的有向圖深度優先搜尋

圖的深度優先搜尋類似。但是對於有向圖或有向圖，我們可以找到一些型別的邊。DFS演算法形成一棵稱為DFS樹的樹。有四種類型的邊，稱為 -

  • 樹邊 (T) - 存在於DFS樹中的那些邊

  • 前向邊 (F) - 與一組樹邊平行。（從較小的DFS編號到較大的DFS編號，以及較大的DFS完成編號到較小的DFS完成編號）

  • 後向邊 (B) - 從較大的DFS編號到較小的DFS編號，以及較小的DFS完成編號到較大的DFS完成編號。

  • 橫向邊 (C) - 較大的DFS編號到較小的DFS編號，以及較大的DFS完成編號到較小的DFS完成編號。

假設我們有一個如下所示的圖 -

現在我們將以A作為初始頂點執行DFS，並輸入DFS編號和DFS完成編號。因此，樹將如下所示 -

所以DFS遍歷是A、B、F、D、G、C、E

樹邊為 - T = {(A, B), (B, F), (F, D), (F, G), (A, C), (C, E)}

前向邊為 - F = {(A, G)}

後向邊為 - B = {(G, B)}

橫向邊為 -C = {(G, D)}

更新於: 2020年8月10日

549 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告