2

当我在无向图上使用深度优先搜索来确定 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;
}

我想一定有一些无限调用内存不足，但我找不到它。

4

4 回答 4

4

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

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

于 2013-02-07T02:56:25.653 回答
2

这就是问题

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

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

于 2013-02-07T02:57:51.107 回答
1

使用您的算法，如果图形有一个循环，它将继续将循环的元素推入堆栈，直到内存不足。您需要跟踪哪些节点已经被探索并避免将它们推入堆栈。有几种标准算法可以做到这一点（我想到了A *和 Dijkstra）。有关更多信息，请参阅有关深度优先搜索的 Wikipedia 文章。

于 2013-02-07T02:56:23.213 回答
0

尝试使用额外的

List<Nodes> 遍历 = new ArrayList<Nodes>();

在这种情况下，您可以保留要推送到堆栈的节点。在将其推入堆栈之前执行 1 步

if(!traversed.contains(temp)) {
stack.push(temp);
}
于 2013-02-07T06:42:31.567 回答