我读了一篇关于在有向图中寻找循环的讨论现在，OP声称我们需要验证两件事：
有一条从u到v的后缘v在递归堆栈中
为什么我们需要第二次测试？你能举个例子说明这是必要的吗？
最佳答案
好吧，你可能混淆了有向图的后边和无向图的后边的定义。是的，它们是不同的。
在无向图中，后边是从当前顶点到已访问顶点的边。（如链接中的op所述）。
在有向图中，后边的定义是不同的。有向图的后边是从当前顶点到灰色顶点的边（该顶点的DFS已开始但尚未完成），这意味着它仍在递归堆栈中。
所以如果你把后边定义为有向图中的后边，那么是的，这就足够检测一个循环了。
但是，如果将后边的定义作为无向图中的后边，则还需要确保v在递归堆栈中，以便检测循环。
有关更多信息和示例，请参见this和this。
例子：
将dfs访问顺序设为A -> B -> C。
在本例中，edge<A,C>是underrestricted图中的后边（因为C已经被访问过）。
但它不是这个有向图的后边-C已经被访问过，但不在递归堆栈中，这意味着它不是一个循环。
关于algorithm - 在有向图中检测周期，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39435604/