java - 深度优先搜索遇到 java.lang.OutOfMemoryError

Question

当我在无向图上使用深度优先搜索来确定节点 1 是否可以到达节点 2 时，我遇到了 java.lang.OutOfMemoryError 。代码如下所示。 (一些不相关的细节将被删除。)

    //definition of nodes and edges
    Set<Node> nodes = new HashSet<Node>();
    Map<Node, Set<Node>> edges = new HashMap<Node, Set<Node>>();

    //method to determine if node1 is reachable to node2    
    public boolean isReachable(int p1, MethodNode m1, ClassNode c1, int p2, MethodNode m2, ClassNode c2) {  
            Node node1 = new Node (p1,m1,c1);
        Node node2 = new Node (p2,m2,c2);

            Stack<Node> stack = new Stack<Node>();

        stack.push(node1);
        while(!stack.isEmpty()){

            Node current = null;
            current = stack.pop();
                    //test current node, if its child nodes contains node2, return true
                    //otherwise, push its child nodes into stack
            for(final Node temp : edges.get(current)){
                if(temp.equals(node2)){
                    return true;
                }
                else{
                    stack.push(temp);
                }
            }
        }
        return false;
}

我猜一定有一些无限调用耗尽了内存，但我找不到它。

Answer 1

看起来您的代码很容易追逐自己的尾部:如果图形包含循环，您的代码将耗尽堆栈，因为它在将顶点插入堆栈之前不会检查顶点是否已被探索。

Basic DFS要求您维护一组已探索的顶点，并且仅在未探索的情况下才探索顶点。将此集添加到您的程序中应该可以解决内存不足问题。