检测有向图中的循环

Question

我在这里读到了一篇关于在有向图中寻找循环的讨论。现在，OP 声称我们需要验证两件事：

1. u从到有一个后缘v
2. v位于递归堆栈中

为什么我们需要第二次测试？您能举个例子来证明它的必要性吗？

Answer 1

好吧，您可能对有向图中的后边和无向图中的后边的定义感到困惑。是的，它们是不同的。

而在无向图中，后边是从当前顶点到已访问顶点的边。（正如您提到的链接中的OP）。
在有向图中，后沿的定义是不同的。有向图中的后边是从当前顶点到灰色顶点的边（该顶点的 DFS 已开始但尚未完成），这意味着它仍在递归堆栈中。

因此，如果您采用有向图中后沿的定义，那么是的，这足以检测循环。
但是，如果您采用无向图中后沿的定义，那么您还需要确保它v位于递归堆栈中才能检测循环。

请参阅此和此以获取更多信息和示例。

示例：
考虑 DFS 访问顺序为A -> B -> C。
在此示例中，该边<A,C>是下图中的后边（因为 C 已被访问）。
但它不是这个有向图中的后沿 - C 已被访问但不在递归堆栈中，这意味着它不是循环。