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

これにより、スタック上のすべてのネイバーがプッシュされ、次にそれらの 1 つが取得され、スタック上のすべてのネイバー (開始したものを含む) がプッシュされ、というように無限に繰り返されます。これが起こらないように、ノードを訪問済みとしてマークする必要があります。無限ループにならない唯一のケースは、探しているノードが開始ノードに直接隣接している場合、またはノードへのパス上のノードが正しい順序でスタックに置かれている場合です。純粋なチャンス。

于 2013-02-07T02:57:51.107 に答える
1

アルゴリズムでは、グラフにサイクルがある場合、メモリが不足するまで、サイクルの要素をスタックにプッシュし続けます。どのノードがすでに探索されているかを追跡し、それらをスタックにプッシュしないようにする必要があります。これを行うためのいくつかの標準的なアルゴリズムがあります（A *とダイクストラが思い浮かびます）。詳細については、深さ優先探索に関するWikipediaの記事を参照してください。

于 2013-02-07T02:56:23.213 に答える
0

エクストラを使ってみる

List< Nodes > traversed = new ArrayList< Nodes >();

これにより、プッシュしているノードをスタックに保持できます。スタックにプッシュする前に 1 ステップを実行する

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