algorithm - 检测有向图中的循环

Question

我阅读了一个讨论 here ，关于在有向图中找到一个循环。现在，OP 声称我们需要验证两件事:

1. 从 u 到 v 有一条后缘
2. v 在递归栈中

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

Answer 1

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

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

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

参见 this和 this获取更多信息和示例。

示例:
考虑 DFS 访问顺序为 A -> B -> C .
在此示例中，边 <A,C>是下标图中的后边(因为 C 已经被访问过)。
但它不是这个有向图中的后边 - C 已经被访问过但不在递归堆栈中，这意味着它不是循环。