有没有一种有效的算法来检测有向图中的循环?
我有一个有向图,表示需要执行的作业计划,作业是一个节点,依赖项是一个边。我需要检测这个图中导致循环依赖关系的循环的错误情况。
有没有一种有效的算法来检测有向图中的循环?
我有一个有向图,表示需要执行的作业计划,作业是一个节点,依赖项是一个边。我需要检测这个图中导致循环依赖关系的循环的错误情况。
当前回答
Tarjan的强连通分量算法的时间复杂度为O(|E| + |V|)。
有关其他算法,请参见维基百科上的强连接组件。
其他回答
我的方法是做一个拓扑排序,计算访问顶点的数量。如果这个数字小于DAG中的顶点总数,那么就有一个循环。
我已经在sml(命令式编程)中实现了这个问题。这是大纲。找到所有入度或出度为0的节点。这样的节点不能成为循环的一部分(因此将它们删除)。接下来,从这些节点中删除所有传入或传出边。 递归地将此过程应用于结果图。如果最后你没有剩下任何节点或边,图就没有任何循环,否则就有。
Tarjan的强连通分量算法的时间复杂度为O(|E| + |V|)。
有关其他算法,请参见维基百科上的强连接组件。
如果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中提供了一个图形着色的实现