Wie man dieses Stapelüberlaufproblem beim Auffinden von SCCs überwinden kann?

Question

Dies ist der Code, den ich schrieb, um SCCs usingg Kosaraju Two-Passed-Algorithmus zu finden. Wenn ich die Hauptmethode ausführe, bekomme ich einen StackOverFlowError auf SCC.revDFS. Wie kann ich den Stapelüberlauffehler vermeiden, wenn viele rekursive Aufrufe ausgeführt werden?

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

Vielleicht können Sie versuchen, die Logik zu iterativen Ansatz zu konvertieren. Überprüfen Sie außerdem, ob die Base- und Edge-Cases ordnungsgemäß verarbeitet wurden.

Answer 2

Die Grundidee zum Konvertieren einer rekursiven Funktion in eine iterative Funktion besteht darin, dass eine rekursive Funktion Argumente von einem Stapel konsumiert.

Sie können also einen Stapel erstellen und die Werte hineinschieben und dann in einer Schleife konsumieren.

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

Ich kann es nicht wirklich testen, um zu sehen, ob ich einen Fehler irgendeiner Art und revDFS ist eine Funktion, mit viel Nebeneffekt gemacht, und es hat keinen Wert zurück, so Grund ein bisschen schwierig ist, damit.

Aber das Wesentliche ist, dass Sie die Kantenindizes einfach auf den Stapel schieben und dann konsumieren können, anstatt die Funktion selbst aufzurufen.

das Kind Kanten werden in umgekehrter Reihenfolge verarbeitet werden, so dass, wenn Sie die gleiche Reihenfolge der Bearbeitung des Originals behalten möchten Sie die Kanten in umgekehrter Reihenfolge sollte lauten:

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

Answer 3

Sie Ihre Dfs Funktion implementiert haben rekursiv was "Stapelüberlauf" verursacht. Um dieses Problem zu beheben, müssen Sie es mithilfe der Stack-Datenstruktur implementieren. siehe Link unten für weitere Motivationen https://github.com/sinamalakouti/MyFavoriteAlgorithmProblems