有没有一种有效的算法来检测有向图中的循环?
我有一个有向图,表示需要执行的作业计划,作业是一个节点,依赖项是一个边。我需要检测这个图中导致循环依赖关系的循环的错误情况。
有没有一种有效的算法来检测有向图中的循环?
我有一个有向图,表示需要执行的作业计划,作业是一个节点,依赖项是一个边。我需要检测这个图中导致循环依赖关系的循环的错误情况。
当前回答
假设这是一个作业时间表,我怀疑在某些时候您会将它们按照建议的执行顺序进行排序。
如果是这种情况,那么拓扑排序实现在任何情况下都可以检测到循环。UNIX tsort当然可以。因此,我认为在三步排序的同时检测循环比在单独的步骤中检测更有效。
因此,问题可能变成“我如何最有效地进行tsort”,而不是“我如何最有效地检测循环”。答案可能是“使用图书馆”,但如果没有下面的维基百科文章:
http://en.wikipedia.org/wiki/Topological_sorting
有一种算法的伪代码,以及来自Tarjan的另一种算法的简要描述。两者都具有O(|V| + |E|)时间复杂度。
其他回答
我的方法是做一个拓扑排序,计算访问顶点的数量。如果这个数字小于DAG中的顶点总数,那么就有一个循环。
如果你不能给节点添加一个“被访问过”的属性,使用一个集合(或者映射),把所有被访问过的节点添加到集合中,除非它们已经在集合中。使用唯一的键或对象的地址作为“键”。
这还为您提供了关于循环依赖项的“根”节点的信息,当用户必须修复问题时,这些信息将派上用场。
另一个解决方案是尝试找到下一个要执行的依赖项。为此,您必须有一个可以记住您现在在哪里以及接下来需要做什么的堆栈。在执行依赖项之前,检查它是否已经在此堆栈上。如果是,你就找到了一个循环。
虽然这看起来可能有O(N*M)的复杂度,但你必须记住,堆栈的深度非常有限(所以N很小),而且随着你可以检查为“已执行”的每个依赖项,M会变得越来越小,加上你可以在找到叶子时停止搜索(所以你永远不必检查每个节点-> M也会很小)。
在MetaMake中,我将图表创建为列表列表,然后在执行它们时删除每个节点,这自然地减少了搜索量。实际上,我从来不需要运行一个独立的检查,这一切都是在正常执行过程中自动发生的。
如果你需要一个“仅测试”模式,只需添加一个“干运行”标志,它禁止实际作业的执行。
https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length我最喜欢这个解决方案,特别是4个长度:)
物理向导还说你必须做O(V^2)。我相信我们只需要O(V)/O(V+E)。 如果图是连通的,那么DFS将访问所有节点。如果图有连通的子图,那么每次我们在这个子图的顶点上运行DFS时,我们都会找到连通的顶点,并且不必为下一次运行DFS考虑这些。因此,对每个顶点运行的可能性是不正确的。
在我看来,在有向图中检测周期最容易理解的算法是图着色算法。
基本上,图着色算法以DFS方式(深度优先搜索,这意味着它在探索另一条路径之前完全探索一条路径)遍历图。当它找到后边缘时,它将图形标记为包含循环。
有关图着色算法的深入解释,请阅读这篇文章:http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/
另外,我在JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js中提供了一个图形着色的实现
我已经在sml(命令式编程)中实现了这个问题。这是大纲。找到所有入度或出度为0的节点。这样的节点不能成为循环的一部分(因此将它们删除)。接下来,从这些节点中删除所有传入或传出边。 递归地将此过程应用于结果图。如果最后你没有剩下任何节点或边,图就没有任何循环,否则就有。