基于DFS的有向图环检测算法是否存在隐藏问题？

问题本质 #

你提到的仅用visited[]数组的DFS实现不可靠，会在无环有向图中误判存在环。核心原因是：单一visited[]只能记录节点是否被访问过，但无法区分「当前递归遍历路径（栈）中的节点」和「已经处理完毕的节点」。有向图的环定义是在同一条遍历路径中回到已访问的节点，而非任意已访问节点。

反例（无环图被误判为有环） #

构造如下无环有向图：

• 边列表：A→B, A→C, C→B

当你的DFS按以下顺序遍历：

1. 访问节点A，标记visited[A] = true
2. 递归访问节点B，标记visited[B] = true，B无后续节点，回溯
3. 回到A，访问节点C，标记visited[C] = true
4. 递归访问节点B，此时发现visited[B] = true，你的算法会直接判定存在环，但实际上这是无环图，只是存在多条路径到达B。

正确的改进方案 #

需要额外维护一个recursionStack[]数组（或用三状态标记：未访问/正在访问/已访问），跟踪当前递归栈中的节点。只有当遍历到的节点处于当前递归栈中时，才判定存在环。

改进后的核心代码片段 #

public class DirectedCycleDetection {
    private List<List<Integer>> adj;
    private boolean[] visited;
    private boolean[] recursionStack;

    public DirectedCycleDetection(int vertices, int[][] edges) {
        adj = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
        }
        visited = new boolean[vertices];
        recursionStack = new boolean[vertices];
    }

    public boolean hasCycle() {
        for (int i = 0; i < adj.size(); i++) {
            if (!visited[i]) {
                if (dfs(i)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(int node) {
        visited[node] = true;
        recursionStack[node] = true;

        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                if (dfs(neighbor)) {
                    return true;
                }
            } else if (recursionStack[neighbor]) {
                // 仅当邻居在当前递归栈中时，才判定有环
                return true;
            }
        }

        recursionStack[node] = false; // 回溯，移出递归栈
        return false;
    }
}

测试验证说明 #

你之前的测试用例可能没覆盖到「无环但存在多路径到同一节点」的场景，所以才会得到符合预期的结果。用上面的反例测试你的原始算法，就会出现误判。

内容的提问来源于stack exchange，提问作者Игорь Райский