正確的DFS遍歷

，因爲它是圖的DFS遍歷，我們使用棧，所以我參觀了一個，因爲它在問題的定則我去了B，因爲它是一個有向圖，然後到C，因爲C沒有任何其他方向，所以我不得不回到我的堆棧，即B現在我去了D現在D要麼導致C，要麼我必須退回到我的堆棧所以我搬到了B（因爲我已經訪問過C）B再次疲憊，所以我回到了A，現在我的A把我引向F，它是可逆的G，H甚至沒有鏈接，所以它是正確的方式忽視他們或我應該訪問他們？什麼應該是正確的DFS遍歷答案？

來源

2017-07-22 Paul Stoner

@JonChesterfield夥計，我已經學嘗試我無法真正理解的答案是否正確，如果錯了，做這件事的正確方法是什麼？在投票或甚至評論垃圾之前，請閱讀問題兩次。 –

DFS/BFS背後的概念是，您應該只在遍歷不連接的節點時訪問連接的節點，這樣確實訪問的節點是正確的，並且訪問的順序也是正確的，但您應該嘗試使堆棧表示有點清晰，因爲很難確定如何在映像中跟蹤堆棧以適應您的嘗試。

來源

2017-07-22 17:24:15

表示DFS遍歷的最好方法是構建相應的生成樹。

在你的問題圖可以用鄰接表示的圖列出方式：

A: B, C, F 
B: C, D 
C: 
D: A, C 
E: C, G 
F: A, C 
G: E

一個DFS從一開始將只能訪問A，B，C，d和F產生以下跨越樹：

您可以添加到這個樹中的未使用的邊緣（那些被忽略，因爲它們會導致媒體鏈接訪問頂點），甚至給他們的分類（前部邊緣，後邊緣和交叉邊緣。）但是，跨越TRE電子可能就足夠了。

對於更一般的考慮：一個DFS是可以這樣描述一個遞歸程序（可以使用堆棧來模擬）：

DFS(g, cur, mark): 
    mark[cur] = True 
    foreach s in successors of cur in g: 
    if not mark[s]: 
     DFS(g, s, mark)

但是你應該已經知道了......

編輯：這是蟒蛇一個簡單的實現產生用於構建圖中的點：

https://gist.github.com/slashvar/d4954d04352fc38356f774198e3aa86b

來源

2017-07-22 17:53:04

不會有F？ –

是的，我忘了A的繼任者中的F ...我會嘗試糾正我的回答 –

我認爲它應該是A，B，C，D，F –

正確的DFS遍歷

回答

相關問題