CODEWITHSUNDEEP
java
Patrick N
Patrick N

Reputation: 143

Graph DFS in Java giving stack overflow error on large input

This is for a homework problem- for a given undirected graph, if it is 2-colorable, color it, and if not, output some odd-length loop within it. This method goes through, coloring as it goes, and if it finds a loop it pops back up the stack and outputs the loop. It works fine for a small input, but on a large input gives a stack overflow error. Is there anything I can do to get it to not overflow with a large input?

P.S. I know I should be using getter and setter methods for the variables in Node. Children is a list of all nodes with an edge to the given node.

public static boolean isOddLoop(Node current){
    for(int x=0; x<current.children.size(); x++){
        Node next = current.children.get(x);
        if(next.color==0){ //i.e. is unvisited
            next.color=3-current.color; //colors are 1 and 2, so this sets it to the opposite
            if(isOddLoop(next)){
                System.out.println(current.number + ": " + current.color);
                return true;
            }   
        }
        if(next.color==current.color){
            System.out.println(next.number + ": " + next.color);
            System.out.println(current.number + ": " + current.color);
            return true;
        }
    }
    return false;
}

Upvotes: 0

Views: 361

Answers (1)

11th Hour Worker
11th Hour Worker

Reputation: 379

As a comment above says, increasing the memory allocated to your JVM stack will definitely alleviate the problem. See this post here for help on that Java stack overflow error - how to increase the stack size in Eclipse?

A better solution in my opinion is to switch to BFS instead of DFS. Using BFS is also a valid solution for the 2-coloring problem. Furthermore, BFS can be done with a queue and no recursion. Then, you'd have a far smaller stack and be limited by your heap size instead. Note that since you no longer have a stack to keep track of the parent node, you'll need to add a pointer for the parent node in the node class and update it as you go.

Upvotes: 1

Related Questions