java - DFS导致堆栈溢出

Question

我在一个有72万个顶点对的数据文件中编写了一个关于dfs的简单代码，并发现堆栈溢出。我不太确定这是由大数据集还是我的代码问题引起的。任何想法表示赞赏。代码部分如下所示:

private void dfs(Graph G, int v) {
    dfsMarked[v] = true;
    for (Edge e : G.adj(v)) {
        int w = e.other(v);  
        if (!dfsMarked[w]) {
            dfsEdgeTo[w] = v;
            dfs(G, w);
        }
    }
}

Answer 1

72 万个顶点对，一次遍历几十万个顶点对，在大多数系统上很容易溢出堆栈。

您需要切换到使用独立于 Java 堆栈分配的您自己的堆栈的 DFS 实现:

Stack<Integer> stack = new Stack<Integer>();
stack.push(start);
while (!stack.empty()) {
    int v = stack.pop();
    dfsMarked[v] = true;
    for (Edge e : G.adj(v)) {
        int w = e.other(v);  
        if (!dfsMarked[w]) {
            dfsEdgeTo[w] = v;
            stack.push(w);
        }
    }
}

注意:上面假设邻接表是无序的。如果您需要保留特定顺序以匹配递归版本，请更改嵌套循环以反向枚举邻接列表。