java - 深度优先搜索正在运行到java.lang.OutOfMemoryError

当我在无向图上使用深度优先搜索来确定node1是否可到达node2时，我遇到了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;
}

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

最佳答案

这就是问题

for (final Node temp : edges.get(current)){
    if(temp.equals(node2)){
        return true;
    } else {
        stack.push(temp);
    }
}

这将推动堆栈中的所有邻居，然后选择其中的一个，将其所有邻居（包括您开始时的邻居）推入堆栈，依此类推。您需要将节点标记为已访问，这样就不会发生。唯一不会出现无限循环的情况是，当您要查找的节点与您开始的节点直接相邻时，或者如果将其路径上的节点按照正确的顺序放入堆栈中，纯粹的机会。