有向图圈检测的最佳算法

Question

有向图圈检测的最佳算法在有向图中检测所有圈的最有效算法是什么？我有一个有向图，表示需要执行的作业计划，作业是节点，依赖项是边。我需要检测这个图中导致循环依赖的循环的错误情况。

Answer 1

最简单的方法就是对图进行深度优先遍历(DFT).

如果图有n顶点，这是O(n)时间复杂度算法由于您可能需要从每个顶点开始执行dft，所以总复杂度将变为O(n^2).

你必须保持包含当前深度第一次遍历中所有顶点的堆栈，它的第一个元素是根节点。如果您在DFT期间遇到一个已经在堆栈中的元素，那么您就有了一个循环。