图中环检测

伪代码

有向图和无向图需要的检测方法确实不同。有向版本追踪递归栈，无向版本追踪父结点。

// 有向：三色 DFS
白 = 未访问，灰 = 在递归栈中，黑 = 已完成

有环(u):
    颜色[u] = 灰
    对 u 的每个邻居 v:
        若 颜色[v] == 灰: 返回真      // 回边
        若 颜色[v] == 白 且 有环(v):
            返回真
    颜色[u] = 黑
    返回假

// 无向：携带父结点的 DFS
有环(u, 父):
    已访问.加入(u)
    对 u 的每个邻居 v:
        若 v == 父: 跳过
        若 v 在已访问中: 返回真
        若 有环(v, u): 返回真
    返回假

这个区别比看上去更重要。在有向图中，抵达一个黑色结点是横叉边，完全不构成环，因此朴素的已访问检查会报告并不存在的环。在无向图中，跳过父结点正是防止把每一条边都读成双结点环的关键。

分步示例演算

在一个既含环又含一条误导性横叉边的图上运行有向三色检测。

示例图: 有向边 A 到 B、A 到 C、B 到 D、C 到 D 以及 D 到 B。

1. 进入 A. 颜色[A] = 灰。取第一个邻居 B。
2. 进入 B. 颜色[B] = 灰。它唯一的邻居是 D。
3. 进入 D. 颜色[D] = 灰。它的邻居是 B，而颜色[B] 为灰。B 位于当前递归栈中，因此 D 到 B 是一条回边，环 B 到 D 到 B 得到确认。
4. 朴素版本会怎么做. 假设不存在 D 到 B 这条边。D 会以黑色完成，控制回到 A，随后 A 到 C 到 D 会发现 D 已被访问。朴素的已访问检查会把它当作环。但它不是：那是一条通往已完成子树的横叉边，三色检测因为 D 是黑而非灰，正确地忽略了它。

该图确实含有一个环 B 到 D 到 B，由灰色检测找出。路径 A 到 C 到 D 并不是环，而区分这两种情形的唯一依据就是颜色。

复杂度及其来源

时间: O(V + E) · 空间: O(V)

两种写法都是单次 DFS，每条边只做常数级的额外工作，因此代价与遍历本身相同。颜色数组或已访问集合为 O(V)，再加 O(V) 的递归栈。针对无向图的并查集替代方案运行在 O(E alpha(V))，实际上是线性的；当边逐条到达、而你希望在边出现的那一刻就拒绝掉闭合环的边而不必重新遍历整个图时，它更为合适。

何时使用环检测，何时不宜

选择检测方法时，既要匹配边的方向，也要考虑图是静态的还是逐步构建的。

常见陷阱

• 在有向图上使用无向图的检测方法. 这是环检测中最常见的错误。在有向图上，朴素的已访问检查会因任何通往已完成子树的横叉边而报告存在环。请使用三色标记，或把递归栈作为单独的集合维护。
• 忘记重置递归栈标记. 结点完成时必须把灰改为黑。留下灰色结点会使之后通往它们的任何路径都看起来像回边，从而在第二个及以后的 DFS 起点上产生误报。
• 不在非连通分量上重新开始. 从一个源点出发的 DFS 只能看到一个分量。环可能位于你从未进入的分量中，因此要遍历所有结点，并从每个仍未访问的结点重新启动 DFS。
• 自环与平行边. 自环是长度为一的环，父结点检查无法发现它。无向多重图中同一对结点之间的两条平行边构成长度为二的环，但无条件跳过父结点会把它掩盖。应当只跳过父边一次，而不是跳过它的每一次出现。

常见问题

如何检测有向图中的环？

运行一次把结点标成白、灰、黑三色的 DFS。结点在位于当前递归栈中时为灰，完成后为黑。指向灰色结点的边是回边，证明存在环；指向黑色结点的边是横叉边或前向边，什么也证明不了。整个检测为 O(V + E)。

如何检测无向图中的环？

运行携带父结点的 DFS。若抵达一个已访问且不是父结点的结点，该边就闭合了一个环。另一种做法是并查集：逐条处理边，一旦某条边的两个端点已在同一集合中，就报告存在环。

为什么已访问检查在有向图上会失效？

因为已访问只说明该结点先前被抵达过，并不说明它是当前结点的祖先。在图 A 到 B、A 到 C、B 到 D、C 到 D 中并没有环，但朴素的已访问检查会因为 D 先前已通过 B 被看到而标记 C 到 D 这条边。你需要知道的是目标是否仍在递归栈中。

检测环最快的方法是什么？

对静态图而言，单次 O(V + E) 的 DFS 已是最优，因为至少要把输入读一遍。对逐条构建的无向图而言，并查集在实践中更好，因为每条新增的边都能以近似常数时间检验，无需重新遍历。

DAG 可能包含环吗？

按定义不可能。有向无环图恰恰就是不含环的有向图，因此环检测是拓扑排序之前的标准有效性检查。若存在环，就不存在任何合法的拓扑序。