使用贪婪算法访问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中的所有节点

回答

相关问题