CODEWITHSUNDEEP
javagraphdepth-first-searchstack-overflow
Mocking
Mocking

Reputation: 1894

StackOverflowError -java

I am writing a code to run DFS on a graph however these graphs are huge. I am getting a stack overflow error on DFS visit however other people were able to run DFS visit without any problems. Is there any reason why I would be getting a StackOverFlow error? I tried allocating more memory (I have 16gb RAM) however it caps me at 1gb ram.

public void DFSVisit(Graph <String, String> graph, String current, int [] data, StackObject [] finish, boolean complicated){
    //data stores the time
    data[9]++;
    graph.setAnnotation(current, "time", data[9]);
    graph.setAnnotation(current, "color", "gray");
    Iterator <ArrayList<String>> itr = graph.outAdjacentVertices(current);
    ArrayList <String> currentlist = null;
    String adjacent;
    while(itr.hasNext()){
        currentlist = itr.next();
        adjacent = currentlist.get(1);
            if(graph.getAnnotation(adjacent, "color").equals("white")){
                graph.setAnnotation(adjacent, "parent", current);
                DFSVisit(graph, adjacent, data, finish, complicated);
            }
    }
    graph.setAnnotation(current, "color", "black");
    data[9]++;
    graph.setAnnotation(current, "done", data[9]);
    finish[0].done.push(current);
    //System.out.println(current);
}

Upvotes: 0

Views: 94

Answers (4)

Mocking
Mocking

Reputation: 1894

I switched over to working on my laptop and it worked immediately. Apparently the problem was me using a 32 bit Eclipse instead of a 64 bit Eclipse. I didn't even realize I was using a 32 bit on my desktop.

Upvotes: 0

Niraj Patel
Niraj Patel

Reputation: 2208

You have to stop recursive calls on some point..with some condition..otherwise it will be endless calls and will throw stack-overflow error.

Upvotes: 1

Mohsen Kamrani
Mohsen Kamrani

Reputation: 7457

please note that the space complexity of the DFS is O(b.m) where m is depth of the search space and b is the maximum branching factor, so if m is infinite, you may never be able to solve the problem with an inappropriate implementation.

To find a better example, look at this question on SO.

Upvotes: 0

Chamawarna
Chamawarna

Reputation: 56

Allocating memory will not help. You call DFSVisit inside same method and no return condition defined for the method hence it will throw stackoverflow error.

Upvotes: 1

Related Questions