java.lang.StackOverflowError due to iterator in DFS

Question

I am currently trying to make a graph represantation of a game by creating the graph class by myself. The constructor is this one (hope I dont have any logic mistake here):

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

I check if there is a path between a source and destination by using the depth first search algorithm. This is what I wrote:

 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

The problem is that when I run this method in a main class , I have this error:

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)

line 67 is:

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

And line 74 is the recursive call:

if(hasPath(n, dest))

I read about StackOverflowError and it had something to do with lack of memory available , I understand that one and my question is not that. But I don't understand why it should happen here cause of the iterator. I tried it even with nodes that are close to each other which make just a few recursive calls, and the same error occurs.

You never check wether or not you have alraedy visited the node. You only mark it as viisited, but when you encounter it again you check it again => infinite recursion. — Polygnome, Jun 04 '17 at 17:22
Add a `println()` statement at the beginning of method `hasPath()`, printing both parameters. The output will help identify why your code fails. This is called **debugging**. You might also want to read "[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5221149)", though a simple `print` statement is likely the easier way to see the problem. — Andreas, Jun 04 '17 at 17:46

score 1 · Accepted Answer · answered Jun 04 '17 at 17:33

1

Before going into recursive call check if you have already covered that node by using

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

answered Jun 04 '17 at 17:33

Deepankar Singh

662
1
9
20

java.lang.StackOverflowError due to iterator in DFS

1 Answers1