确认基于迭代DFS的有向图环检测代码的时间与空间复杂度

实现代码 #

import java.util.*;

class Program {
    public boolean cycleInGraph(int[][] edges) {
        // Write your code here.
        int n = edges.length;
        boolean[] visited = new boolean[n];

        Arrays.fill(visited, false);

        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;

            boolean containsCycle =
                helper(edges, i, visited);
            if (containsCycle) return true;
        }
        return false;
    }
    public boolean helper(int[][] edges, int i, boolean[] visited) {
        Set<Integer> set = new HashSet<>();
        Stack<Map.Entry<Integer, Set<Integer>>> s = new Stack<>();
        set.add(i);
        s.push(new AbstractMap.SimpleEntry<>(i, set));

        while (!s.isEmpty()) {
            Map.Entry<Integer, Set<Integer>> curr = s.pop();
            Set<Integer> path = curr.getValue();
            int node = curr.getKey();
            visited[node] = true;
            if (edges[node].length == 0) path.remove(node);
            for (int children : edges[node]) {
                if (visited[children] && path.contains(children)) {
                    return true;
                }
                Set<Integer> temp = new HashSet<>(path);
                temp.add(children);
                s.push(new AbstractMap.SimpleEntry<>(children, temp));
            }
        }
        return false;
    }
}

问题描述 #

我用栈存储路径的迭代DFS实现了上述有向图环检测的Java代码，想确认这段代码的时间复杂度是否为O(V+E)、空间复杂度是否为O(V)，同时希望理解为什么任意时刻的空间占用都是O(V)。

复杂度分析与解答 #

1. 时间复杂度：并非O(V+E)

你这段代码的时间复杂度是O(V*E)，达不到O(V+E)的高效级别。问题出在每次遍历子节点时，都执行了new HashSet<>(path)来复制当前路径集合——复制操作的时间成本和当前路径的长度成正比。最坏情况下（比如一条链式图，每个节点只有一个子节点），每个节点对应的路径集合大小是O(V)，总共有O(E)次复制操作，最终时间复杂度会膨胀到O(V*E)。

2. 空间复杂度：并非O(V)

这段代码的空间复杂度也是O(V*E)，远高于O(V)。原因同样是栈中每个元素都携带了一个独立的路径集合：当图存在大量分支时，栈中会堆积多个不同的路径副本，每个副本的大小最多是O(V)，而栈中元素的数量最多是O(E)，两者相乘就导致了空间的高消耗。

3. 为什么标准迭代DFS的空间是O(V)？

标准的迭代DFS环检测（正确实现）不会复制路径集合，而是通过一个额外的inPath数组（或类似标记）来记录当前节点是否处于正在遍历的路径中：

• 栈中只存储节点本身（或附带是否已处理的标记），栈的深度最多是O(V)——因为图中最长的无环路径长度不可能超过V-1（否则必然存在环）。
• 加上visited数组和inPath数组的O(V)空间，总空间占用就是O(V)。

优化建议

你可以修改代码，用inPath数组替代路径集合的复制，示例如下：

public boolean helper(int[][] edges, int i, boolean[] visited) {
    boolean[] inPath = new boolean[edges.length];
    Stack<Integer> stack = new Stack<>();
    stack.push(i);
    inPath[i] = true;

    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (visited[node]) {
            inPath[node] = false;
            continue;
        }
        visited[node] = true;
        for (int child : edges[node]) {
            if (!visited[child]) {
                stack.push(node);
                stack.push(child);
                inPath[child] = true;
                break;
            } else if (inPath[child]) {
                return true;
            }
        }
        inPath[node] = false;
    }
    return false;
}

这样修改后，时间复杂度回到O(V+E)，空间复杂度降到O(V)，符合高效DFS的特性。

内容的提问来源于stack exchange，提问作者Cherukuri Surya