SCCを見つける際にこのスタックオーバーフローの問題を克服するにはどうすればよいですか？

Question

これは、コサラジュのTwo-Passedアルゴリズムを使用してSCCを見つけるために書いたコードです。 mainメソッドを実行すると、SCC.revDFSにStackOverFlowErrorが返されます。大量の再帰呼び出しを行う際にスタックオーバーフローエラーを回避するにはどうすればよいですか？

import java.io.InputStreamReader; 
import java.util.ArrayList; 
import java.util.HashMap; 
import java.util.Iterator; 
import java.util.List; 
import java.util.Map; 
import java.util.Arrays; 
import java.util.Scanner; 

public class SCC { 
    int n = 875714; 
    Map<Integer,List<Integer>> adjList; 
    Map<Integer,List<Integer>> adjListRev; 
    int[] ft; 
    int t; 
    int s; 
    boolean[] marked; 
    int[] leaders; 

    public SCC() { 
     init(); 
     t = 0; 
     s = 0; 
     marked = new boolean[n + 1]; 
     leaders = new int[n + 1]; 
    } 

    void init() { 
     adjList = new HashMap<Integer,List<Integer>>(); 
     adjListRev = new HashMap<Integer,List<Integer>>(); 
     ft = new int[n + 1]; 
     List<Integer> adj; 
     try { 
      Scanner scanner = new Scanner (new InputStreamReader(this.getClass(). 
        getClassLoader().getResourceAsStream("SCC.txt"))); 
      while(scanner.hasNextLine()) { 
       String s = scanner.nextLine().trim(); 
       String[] num = s.split(" "); 
       if (!adjList.containsKey(Integer.parseInt(num[0]))) { 
        adjList.put(Integer.parseInt(num[0]), new ArrayList<Integer>()); 
       } 
       adj = adjList.get(Integer.parseInt(num[0])); 
       adj.add(Integer.parseInt(num[1])); 
       adjList.put(Integer.parseInt(num[0]), adj); 

       if (!adjListRev.containsKey(Integer.parseInt(num[1]))) { 
        adjListRev.put(Integer.parseInt(num[1]), new ArrayList<Integer>()); 
       } 
       adj = adjListRev.get(Integer.parseInt(num[1])); 
       adj.add(Integer.parseInt(num[0])); 
       adjListRev.put(Integer.parseInt(num[1]), adj); 
      } 
     } catch (Exception e) { 
      e.printStackTrace(); 
     } 
    } 

    public void DFS_Loop() { 

     for (int i = 1; i < n + 1; i++) { 
      marked[i] = false; 
     } 
     for (int i = n; i > 0; i--) { 
      if (!marked[i]) { 
       revDFS(i); 
      } 
     } 
     for (int i = 1; i < n + 1; i++) { 
      marked[i] = false; 
      leaders[i] = 0; 
     } 
     for (int i = n; i > 0; i--) { 
      if (!marked[ft[i]]) { 
       s = ft[i]; 
       DFS(ft[i]); 
      } 
     } 
    } 

    public void revDFS(int i) { 
     marked[i] = true; 
     List<Integer> edges = adjListRev.get(i); 
     if (edges != null) { 
      for (int j: edges) { 
       if (!marked[j]) { 
        revDFS(j); 
       } 
      } 
     } 
     t += 1; 
     ft[t] = i; 
    } 

    public void DFS(int i) { 
     marked[i] = true; 
     leaders[s] += 1; 
     List<Integer> edges = adjList.get(i); 
     if (edges != null) { 
      for (int j: edges) { 
       if (!marked[j]) { 
        DFS(j); 
       } 
      } 
     } 
    } 

    public static void main(String[] args) { 
     SCC scc = new SCC(); 
     scc.DFS_Loop(); 
     Arrays.sort(scc.leaders); 
     for (int i = scc.n; i < scc.n - 5; i--) { 
      System.out.println(scc.leaders[i]); 
     } 
    } 
} 

Answer 1

おそらく、論理を反復的なアプローチに変換しようとすることができます。また、ベースケースとエッジケースが正しく処理されているかどうかを確認してください。

Answer 2

再帰関数を反復関数に変換する基本的な考え方は、再帰関数がスタックから引数を消費することです。

スタックを作成して値をプッシュし、ループで消費することができます。

public void _revDFS(int _i) { 
    LinkedList<Integer> stack = new LinkedList<>(); 
    stack.push(_i); 

    while(!stack.isEmpty()){ 
     int i = stack.pop(); 
     marked[i] = true; 
     List<Integer> edges = adjListRev.get(i); 
     if (edges != null) { 
      for (int j: edges) { 
       if (!marked[j]) { 
        stack.push(j); 
        //revDFS(j); 
       } 
      } 
     } 
     t += 1; 
     ft[t] = i; 
    } 
} 

私は本当に理由に少し難しいですが、私はいくつかの種類のミスを犯し、revDFSは副作用の多くの機能であり、それが値を返さないかどうかを確認するために、それをテストすることはできませんそれと。

しかし、要点は、関数自体を呼び出す代わりに、スタックにエッジインデックスをプッシュしてから消費するということです。あなたは、元の処理の同じ順序を維持したい場合は、逆の順序でエッジを読まなければならないので、

子エッジは逆の順序で処理されます。

  ListIterator<Integer> li = edges.listIterator(edges.size()); 
      while(li.hasPrevious()){ 
       int j = li.previous(); 
       if (!marked[j]) { 
        stack.push(j); 
        //revDFS(j); 
       } 
      } 

Answer 3

あなたが再帰的に自分のDFS機能を実装しましたスタックオーバーフローが発生します。この問題を解決するには、スタックデータ構造を使用して実装する必要があります。 より多くの動機については、以下のリンクを参照してください。 https://github.com/sinamalakouti/MyFavoriteAlgorithmProblems