algorithm - 检测有向图中周期的最佳算法

Closed. This question is opinion-based。它当前不接受答案。












想改善这个问题吗？更新问题，以便editing this post用事实和引用来回答。

在6个月前关闭。



Improve this question




检测有向图内所有周期的最有效算法是什么？

我有一个有向图，表示需要执行的作业计划，其中作业是节点，而依赖项是边缘。我需要在此图中检测导致循环依赖性的循环的错误情况。

最佳答案

Tarjan's strongly connected components algorithm具有O(|E| + |V|)时间复杂度。

有关其他算法，请参见Wikipedia上的Strongly connected components。

关于algorithm - 检测有向图中周期的最佳算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/261573/