在有向图中检测周期的最佳算法
检测有向图中所有周期的最有效算法是什么？
我有一个有向图，表示需要执行的作业的时间表，作业是一个节点，依赖关系是一个边。 我需要检测此图形中循环的错误情况，从而导致循环依赖性。
Tarjan的强连通组件算法具有O(|E| + |V|)时间复杂度。
对于其他算法，请参阅Wikipedia上的强连接组件。
鉴于这是一份工作时间表，我怀疑在某个时候你会把它们分类为一个建议的执行顺序。
如果是这样的话，那么拓扑排序实现可以在任何情况下检测周期。 UNIX tsort当然可以。 因此，我认为它可能更有效地在循环检测的同时检测循环，而不是单独进行。
所以这个问题可能会变成“我怎样才能最有效地嘲笑”，而不是“我如何最有效地检测循环”。 答案可能是“使用图书馆”，但未能达到以下维基百科文章：
http://en.wikipedia.org/wiki/Topological_sorting
具有一种算法的伪代码，以及来自Tarjan的另一种算法的简要描述。 两者都具有O(|V| + |E|)时间复杂度。
从DFS开始：当且仅当在DFS期间发现后端时才存在循环。 这被证明是白道理论的结果。
链接地址: http://www.djcxy.com/p/70679.html上一篇: Best algorithm for detecting cycles in a directed graph