Comment surmonter ce problème de débordement de pile lors de la recherche de SCC?

Question

C'est le code que j'ai écrit pour trouver des SCCs utilisant l'algorithme à deux passes de Kosaraju. Lorsque j'exécute la méthode principale, j'obtiens un StackOverFlowError sur SCC.revDFS. Comment puis-je éviter l'erreur de débordement de pile lors d'une grande quantité d'appels récursifs?

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

Vous pouvez peut-être essayer de convertir la logique en approche itérative. En outre, vérifiez si vous avez les cas de base et de bord manipulés correctement.

Answer 2

L'idée de base pour convertir une fonction récursive en une fonction itérative est qu'une fonction récursive consomme des arguments d'une pile.

Vous pouvez donc créer une pile et y insérer les valeurs, puis les consommer en boucle.

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

Je ne peux pas vraiment le tester pour voir si je fait une erreur de quelque sorte et revDFS est une fonction avec beaucoup d'effets secondaires et il ne retourne pas une valeur, est donc un peu difficile à la raison avec ça. Mais l'essentiel est que, au lieu d'appeler la fonction elle-même, vous pouvez simplement pousser les index de bord sur la pile, puis les consommer.

Les bords de l'enfant seront traitées dans l'ordre inverse, donc si vous voulez garder le même ordre de traitement de l'original, vous devriez lire les bords dans l'ordre inverse:

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

Answer 3

vous avez mis en place votre fonction Dfs récursive ce qui provoque un "débordement de pile". Pour résoudre ce problème, vous devez l'implémenter à l'aide de la structure de données de la pile. voir le lien ci-dessous pour plus de motivations https://github.com/sinamalakouti/MyFavoriteAlgorithmProblems