DFSによってスタックオーバーフローが発生する

Question

dfsに関する簡単なコードを720,000の頂点ペアを持つデータファイルに書き込み、スタックオーバーフローを検出します。私はそれが大きなデータセットや私のコードの問題によって引き起こされているかどうかはよく分かりません。任意のアイデアが評価されます。コードの一部を下記に示すされています。それらの数百万人にまたがるパスと

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); 
     } 
    } 
} 

注：上記は、隣接リストは順不同であることを前提としています。再帰バージョンと一致するように特定の順序を保持する必要がある場合は、入れ子になったループを変更して隣接リストを逆に列挙します。