java - Java 中的图 DFS 在大输入时出现堆栈溢出错误

Question

这是一个家庭作业问题 - 对于给定的无向图，如果它是 2 色的，则对其进行着色，如果不是，则在其中输出一些奇数长度的循环。该方法会执行，并在运行过程中着色，如果找到循环，则会弹出堆栈并输出循环。它对于小输入工作正常，但对于大输入会出现堆栈溢出错误。我能做些什么来让它不因大输入而溢出吗？

附注我知道我应该对 Node.js 中的变量使用 getter 和 setter 方法。 Children 是与给定节点有边的所有节点的列表。

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

Answer 1

正如上面的评论所说，增加分配给 JVM 堆栈的内存肯定会缓解该问题。请参阅此处的这篇文章以获取有关此问题的帮助 Java stack overflow error - how to increase the stack size in Eclipse?

我认为更好的解决方案是改用 BFS 而不是 DFS。使用 BFS 也是解决 2 着色问题的有效解决方案。此外，BFS 可以通过队列来完成，无需递归。然后，您的堆栈就会小得多，并且会受到堆大小的限制。请注意，由于您不再有堆栈来跟踪父节点，因此您需要在节点类中添加父节点的指针并随时更新它。