有向图圈检测的最佳算法

Question

有向图圈检测的最佳算法

在有向图中检测所有圈的最有效算法是什么？

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

Answer 1

最简单的方法就是对图进行深度优先遍历(DFT).如果图有n顶点，这是O(n)时间复杂度算法由于您可能需要从每个顶点开始执行dft，所以总复杂度将变为O(n^2).你必须保持包含当前深度第一次遍历中所有顶点的堆栈，它的第一个元素是根节点。如果您在DFT期间遇到一个已经在堆栈中的元素，那么您就有了一个循环。