CODEWITHSUNDEEP
javastatic-methodsdepth-first-search
beginner12345
beginner12345

Reputation: 61

Depth First Search is causing a StackOverFlowError

I have an assignment were I have to create run a depth first search through a directed graph, and return the traversal as a linked list. I believe the code for the DFS is correct as it seems to match up with the text book, and as I walk through the steps it makes sense. If I print it out as each vertex gets marked, it keeps printer over and over causing the stack overflow error. 

 private static boolean[] marked;
 private static LinkedList<Integer> ret;

 public static LinkedList<Integer> dfs(Digraph g, int s) {

     marked = new boolean[g.V()];

    ret = new LinkedList<>();

    marked[s] = true;
    System.out.print(s);

    ret.add(s);



   for (int i : g.adj(s)) {
       if (!marked[i]) {
          dfs(g, i);

     }
   }

   return ret;
  }

My guess would be the boolean[] marked is reseting every time I call dfs. I tried putting that outside the method but because the method is static and I can't change it(given the assignment parameters), I was getting a static-non static issue which I'm not quite sure how to fix.

Upvotes: 2

Views: 596

Answers (1)

Gamrix
Gamrix

Reputation: 892

Yup, your issue was indeed because the boolean was being reset in a sense. The resetting was happening in this line:

marked = new boolean[g.V()];

On this line, you are creating a new boolean array in the new function call, which is distinct from the original array . Then you are checking the new array which does not contain the changes from the old array.

I would recommend that you create a wrapper function that initializes the dfs process, and then pass the array into each call of your dfs function.

If you do not want to add extra parameters, just create a static variable as such outside of the method:

private static boolean[] marked;

Then initialize it when appropriate

Upvotes: 2

Related Questions