为何用DFS查找图的强连通分量时会出现StackOverFlowError？

嘿，我来帮你分析下这个问题！你说已经用了visited数组标记访问节点，却还是出现栈溢出，其实这大概率和循环没关系——真正的问题出在递归调用的深度超过了JVM方法栈的容量上限。

问题根源 #

Java的方法调用栈是有固定大小的（默认一般在几百KB到几MB之间，具体看JVM配置）。如果你的测试图是那种超长链式结构（比如1→2→3→…→10000），递归DFS的调用栈会嵌套上万层，直接突破JVM的栈容量限制，触发StackOverFlowError。这种情况哪怕没有循环，照样会出问题。

解决方案：换成迭代版DFS #

最稳妥的办法是把递归DFS改成手动维护栈的迭代版本，用自己的栈替代JVM的方法调用栈，彻底摆脱栈容量限制。

给你调整后的迭代版代码：

static void dfs(int src, boolean[] visited, Stack<Integer> stack) {
    // 手动创建DFS用的栈，存储待处理节点
    Stack<Integer> dfsStack = new Stack<>();
    // 额外数组标记节点是否已处理完成（入栈≠处理完）
    boolean[] processed = new boolean[visited.length];
    
    dfsStack.push(src);
    visited[src] = true;
    
    while (!dfsStack.isEmpty()) {
        int current = dfsStack.peek();
        if (!processed[current]) {
            // 先标记为待处理，再遍历邻接节点
            processed[current] = true;
            // 倒序遍历邻接表，保证和递归版的输出顺序一致（可选）
            List<Integer> adjList = adj[current];
            for (int i = adjList.size() - 1; i >= 0; i--) {
                int neighbor = adjList.get(i);
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    dfsStack.push(neighbor);
                }
            }
        } else {
            // 所有邻接节点处理完毕，再压入结果栈
            stack.push(current);
            dfsStack.pop();
        }
    }
}

额外小提示 #

如果只是临时测试，你也可以通过JVM参数增大栈容量（比如加-Xss4m把栈设为4MB），但这只是权宜之计——遇到更大的图还是会溢出，迭代版才是通用解法。

另外，强连通图判断一般用Kosaraju算法，你现在的代码是第一次DFS的部分，后续别忘了对转置图做第二次DFS哦！

内容的提问来源于stack exchange，提问作者Shreya Jain