訪問和探索（dfs）

的差異我最近嘗試以非遞歸方式實現dfs。我發現有兩個單獨的概念探索節點和訪問節點。有什麼不同？訪問和探索（dfs）

如果我跟蹤節點探索/訪問的順序，各個訂單代表什麼？

2013-11-04 ishan3243

沒有區別。深度第一次搜索訪問每個節點一次，我相信有些人可能會使用'探索'作爲替代術語，但實際上'訪問'更準確。 DFS訪問節點的順序沒有被精確定義 - 如果您有當前節點的多個子節點，您可以按任意順序遞歸節點，每個順序會導致訪問所有節點的順序不同。但是，如果您已經定義了您的孩子的順序（例如，您將圖表存儲在鄰居列表中），則按此順序訪問孩子會更自然。

來源

2013-11-04 08:26:43

但是在非遞歸dfs中，只要將它們推入堆棧，就必須標記所訪問的節點！ – ishan3243

是的，否則你可能會多次訪問一個節點。你看到了什麼問題？ –

問題是，在遞歸dfs中，節點以不同的方式標記。說我有一張圖。節點A有子節點b，c，d，節點b有子節點e，f。如果dfs（遞歸）從'a'開始，那麼節點被標記爲a-> b-> e-> f-> c-> d但是以迭代形式，只要b，c和d被推堆棧，他們被標記訪問。 – ishan3243

訪問和探索（dfs）

回答

相關問題