在有向图中检测循环

Question

我在 Stack Overflow 上读到一个关于查找有向图中的循环的讨论（链接）。现在，楼主声称我们需要验证两件事情：

1. u 到 v 有一条反向边
2. v 在递归栈中

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

- Elimination

Answer 1

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

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

因此，如果您按照有向图中的反向边的定义，那么是足以检测到循环的。 但是，如果您按照无向图中的反向边的定义，那么您还需要确保v也在递归堆栈中才能检测到循环。

请参见此处和此处获取更多信息和示例。 示例： 考虑DFS访问顺序为A -> B -> C。 在这个例子中，边<A,C>是无向图中的反向边（因为C已经被访问过）。 但它不是这个有向图中的反向边——C已经被访问过，但不在递归堆栈中，这意味着它不是一个循环。

- A. Sarid

---

非常感谢你！！ - undefined

Answer 2

仅仅访问了v这个事实是不够的。它允许我们从u到达v，但不能从v到达u。

简单的图形反例：

数字是遍历顺序。我们从4到3有一个反向边，但我们没有任何循环。

- user2512323

Answer 3

第二个测试是在出现横叉边而非回溯边时需要的。横叉边是指从一个顶点到已经访问过的顶点的边，无论位置如何。而回溯边则是指指向起始顶点的祖先（仍在递归栈中）的边。就问题提出的方式而言，OP将指向另一个已经访问过的边的边称为回溯边，但更准确的解释应该是横叉边。知道它是回溯边就足够了，因为它意味着需要进行第二步。当第一步是横叉边时，需要这些步骤，因为第二步证明了横叉边是回溯边。在有向图中，横叉边并不总是意味着发生循环。以下是一个示例：

vertices a,b,c,d
a->b
a->c
b->d
d->c

根据处理的顺序，d->c 可以被视为交叉边，因此需要执行步骤2来检测循环。不幸的是，后向边和交叉边经常混淆，导致这样的困惑。这里有另一个描述两者之间区别的链接深度优先搜索。

- D. Law.

---

谢谢D. Law！ - undefined

我现在明白了，之前的困惑是因为（反向边 vs. 横跨边）。 - undefined

实际上，交叉边并不是你困惑的唯一情况 - 前向边也是一种情况，在无向图中它实际上是一条后向边。在有向图中，你有四种类型的边：后向边、前向边、交叉边和树边。而在无向图中，你只有后向边和树边。 - undefined