java.lang.StackOverflowError dû à l'itérateur dans DFS

Question

Je suis actuellement en train d'essayer de représenter graphiquement un jeu en créant la classe graphique par moi-même. Le constructeur est celui-ci (l'espoir Je n'ai aucune erreur logique ici):

private int nNodes; 
    private int nEdges; 
    private List<Integer> adj[]; 
    private boolean visited[]; 

    public GameGraph() 
    { 
     nNodes = 81; 
     adj = new LinkedList[nNodes]; 
     for(int i = 0; i < nNodes; i++) 
      adj[i] = new LinkedList(); 
     visited = new boolean[nNodes]; 
    } 

Je vérifie s'il y a un chemin entre une source et la destination en utilisant la profondeur premier algorithme de recherche. C'est ce que je l'ai écrit:

public boolean hasPath(int source , int dest) 
     { 
      if(source >= nNodes) 
       return false; 
      else 
      { 
       visited[source] = true; 

       try 
       { 
        Iterator<Integer> iterator = adj[source].listIterator(); 
        while(iterator.hasNext()) 
        { 
         int n = iterator.next(); 
         if(n == dest) 
          return true; 
         visited[n] = true; 
         if(hasPath(n, dest)) 
          return true; 
        }//end while 
        return false; 
       }//end try 
       catch(NullPointerException exception) 
       { 
        exception.printStackTrace(); 
       }//end catch 

       return false; 
      }//end else 
     }//end method has path 

Le problème est que lorsque je lance cette méthode dans une classe principale, j'ai cette erreur:

Exception in thread "main" java.lang.StackOverflowError 
    at java.util.LinkedList$ListItr.<init>(Unknown Source) 
    at java.util.LinkedList.listIterator(Unknown Source) 
    at java.util.AbstractList.listIterator(Unknown Source) 
    at java.util.AbstractSequentialList.iterator(Unknown Source) 
    at logic.GameGraph.hasPath(GameGraph.java:67) 
    at logic.GameGraph.hasPath(GameGraph.java:74)at logic.GameGraph.hasPath(GameGraph.java:74) 
    at logic.GameGraph.hasPath(GameGraph.java:74) 
    at logic.GameGraph.hasPath(GameGraph.java:74) 

ligne 67 est la suivante:

Iterator<Integer> iterator = adj[source].listIterator(); 

Et la ligne 74 est l'appel récursif:

if(hasPath(n, dest)) 

Je lis à propos de StackOverflowError et cela a quelque chose à voir avec le manque de mémoire disponible, je comprends que celui-là et ma question n'est pas ça. Mais je ne comprends pas pourquoi cela devrait se produire ici cause de l'itérateur. Je l'ai essayé même avec des nœuds proches les uns des autres qui ne font que quelques appels récursifs, et la même erreur se produit.

Answer 1

Avant d'entrer dans l'enregistrement d'appel récursif si vous avez déjà couvert ce nœud à l'aide

.... 
int n = iterator.next(); 
if(!visited[n]){ 
... 
}