如何判断图中是否有环？有向图和无向图有什么不同？

简化版

无向图：DFS 时如果遇到一个已访问、且不是当前节点父节点的邻居，就有环；或者用并查集，加一条边时如果两端已经连通，就有环。有向图：DFS 用三色标记，如果遇到一个「正在递归栈中（灰色）」的节点，说明存在指回祖先的边（后向边），就有环；或者用拓扑排序，如果排不完所有节点，就有环。

详细版

无向图环检测

方法一 DFS（记录父节点）：DFS 遍历，如果碰到已访问的邻居，且它不是把我带过来的那个父节点，说明这条边构成了环。

boolean hasCycle(int u, int parent, boolean[] visited, List<List<Integer>> adj) {
    visited[u] = true;
    for (int v : adj.get(u)) {
        if (!visited[v]) {
            if (hasCycle(v, u, visited, adj)) return true;
        } else if (v != parent) {   // 已访问且非父节点 → 有环
            return true;
        }
    }
    return false;
}

方法二并查集：遍历每条边 (u,v)，若 u、v 已在同一集合（已连通），加这条边就成环；否则合并。

有向图环检测

方法一 DFS 三色标记：

白色（0）：未访问。
灰色（1）：正在递归中（在当前 DFS 路径/栈上）。
黑色（2）：已完成（子树全部访问完）。

DFS 时若遇到灰色节点，说明遇到了指向「当前路径上祖先」的边（后向边）→ 有环。

方法二拓扑排序（Kahn）：不断移除入度为 0 的点，如果最后还有点没被移除（入度始终 > 0），说明它们互相成环。

完整版教学

一、为什么有向图和无向图判环方式不同

这是本题的核心考点。无向图的边是双向的：DFS 从 u 走到 v，v 的邻居里必然有 u（因为无向），但这不算环——它只是「原路返回」。所以无向图判环要排除父节点：只有遇到「已访问、且不是父节点」的点才是真环。

有向图的边有方向：从 u 能到 v，不代表从 v 能回到 u。所以「已访问」不足以判环——可能只是从另一条路径访问过（横向边/前向边，不构成环）。有向图的环必须是指回当前递归路径上祖先的边（后向边），所以要用三色标记区分「正在路径上（灰）」和「已彻底完成（黑）」。

二、无向图：DFS 排除父节点

无向图 DFS 判环的关键是传入 parent。遍历 u 的邻居 v：

v 未访问 → 递归，父节点设为 u。
v 已访问且 v ≠ parent → 找到了一条「回到已访问节点」的非返回边，有环。
v 已访问但 v == parent → 只是刚走过来的那条边，跳过。

注意：如果图有重边（两点间多条边），只排一个 parent 可能误判，需要更细致处理。简单图（无重边）用父节点法即可。

三、无向图：并查集判环

并查集判环更简洁，尤其适合「逐条加边」的场景：

初始每个点自成一个集合。
对每条边 (u, v)：如果 find(u) == find(v)（已经连通），那么再加这条边就形成了环 → 有环。
否则 union(u, v) 合并。

Kruskal 最小生成树正是用这个思想避免成环。

四、有向图：三色标记的精髓

有向图 DFS，一个节点有三种状态。关键是区分「灰」和「黑」：

遇到灰色节点：它正在当前 DFS 递归栈里（是当前路径的祖先），现在又有一条边指向它 → 后向边 → 有环。
遇到黑色节点：它的整棵子树都处理完了、已经不在当前路径上，指向它只是「重复到达」，不算环。

如果只用二色（访问/未访问），就会把「黑色」误判成环。三色标记正是为了精确捕捉「指回当前路径」的后向边。

五、有向图：拓扑排序判环

有向图有环 ⟺ 无法完成拓扑排序。用 Kahn 算法：反复移除入度为 0 的节点，成功移除的节点计数。如果最终计数 < 总节点数，说明有一批节点入度始终不为 0（它们互相指、成环），即有环。这个方法还能顺便得到拓扑序，一举两得。

六、常见误区与追问

考点	正确口径
无向图 DFS	访问到已访问且不是父节点的邻居即有环
有向图 DFS	遇到递归栈中的灰色节点即有环
拓扑排序	有向图无法取完所有点说明有环

directed color:
0 = unvisited
1 = visiting
2 = done
edge to color 1 => cycle

无向图要排除来时的父边；有向图要识别是否回到当前递归路径。

误区：无向图看到已访问邻居就一定有环。 如果这个邻居是父节点，那只是沿原边返回，不构成新环。
误区：有向图也能只用 parent 排除法。 有向图的环依赖递归栈状态，必须区分 visiting 和 done。
误区：拓扑排序只能输出顺序，不能判环。 有向图中若最后输出节点数少于 V，说明存在环。
追问：并查集能判哪类环？ 并查集适合无向图，处理边时若两个端点已连通，再加边就成环。
追问：为什么三色法里的灰色重要？ 灰色表示节点还在当前 DFS 路径上，指向灰色就是回边。
追问：复杂度是多少？ 邻接表下 DFS、并查集遍历边、拓扑排序都可做到 O(V+E) 量级。

七、加强记忆

无向图判环：DFS 遇到「已访问且非父节点」的邻居 → 有环（要排除父节点，因为无向边会原路返回）；或并查集加边时两端已连通 → 有环。有向图判环：DFS 三色标记，遇到灰色（正在递归栈上） 节点 → 后向边 → 有环（不能只用二色，会把黑色误判）；或拓扑排序排不完所有节点 → 有环。核心区别：无向排父节点，有向找指回当前路径的后向边。

简化版

详细版