使用貪婪算法訪問DAG中的所有節點

我試圖使用貪婪算法訪問有向無環圖中的所有節點。我在想像深度優先搜索這樣的東西可以工作，但我不確定這將如何與DAG協同工作，因爲我無法通過圖表追溯到自己。使用貪婪算法訪問DAG中的所有節點

謝謝。

來源

2013-03-06 John Smith

如果你只想訪問所有的節點，你爲什麼需要「追溯自己」？ – Raufio 2013-03-06 07:36:24

因爲如果我沒有回溯下圖，這並不一定意味着我會訪問每個節點。 – 2013-03-06 07:37:22

如果它是非循環的並且是直接的，當你用完檢查的節點時，即你到達所有路徑的末端，節點在哪裏存在而不被訪問？ – Raufio 2013-03-06 07:41:40

是的，您可以使用深度優先搜索（DFS）或廣度優先搜索（BFS），檢查任何優秀的texbook，例如Thomas H. Cormen的「Introduction to Algorithms」。

您不需要使用邊來「追溯自己」，使用堆棧（或遞歸）或隊列。

來源

2013-03-06 07:39:38 DixonD

使用調用棧是最直接的實現:-) – 2013-03-06 07:42:27

如果您要檢查Thomas H. Cormen的「算法簡介」，不要害怕開始 - 您不需要閱讀和理解所有內容它 - 這是長期算法學習的好書。 – Ari 2013-03-06 07:42:34

@JanDvorak是的，但你可以很容易地溢出它。你應該謹慎使用call stack :) – DixonD 2013-03-06 07:43:37

void dfs(node V) { 
    mark V as visited; 
    for each edge E, so that E.source = V, do { 
     if(E.destination is not marked as visited) { 
      dfs(E.destination); 
     } 
    } 
}

就是這樣。 DFS（遞歸）的作用是在當前實例完成時返回到其調用者實例。由於它使用堆棧來保存所有活動實例，因此不必自行返回，噹噹前節點上的函數完成執行後，它會自動回滾到前一個節點。

來源

2013-03-06 09:53:02 aram90

您的算法通常是在無向圖中找到一個連接組件所需的。對於DAG，必須通過掃描節點列表並在每個未標記節點上運行dfs執行多次，直到沒有任何此類節點爲止。 – didierc 2013-03-06 12:18:00

是的，如果DAG沒有連接，應該爲每個組件調用，但這就是一切正常的方式，它不會改變主要想法。 – aram90 2013-03-06 15:04:41

使用貪婪算法訪問DAG中的所有節點

回答

相關問題