1

これは、深さ優先検索を使用したグラフの reachable() の実装です。頂点 1 (v1) から別の頂点 (v2) への可能なパスを探します。一部の結果は正しく、一部は間違っています。デバッグするためにできる限り多くの方法を試しましたが、どこが間違っているのかわかりませんでした。どんな助けでも大歓迎です。ありがとうございました

public boolean isReachable(V v1, V v2) {
            Stack<V> path = new Stack<V>();
            return isReachableHelper(v1, v2, path);
        }

}

public boolean isReachableHelper(V v1, V v2, Stack<V> path){
        path.push(v1);
        v1.setVisited(true); //set the vertex as being visited

        if (v1.vertex().equals(v2.vertex())){ //check whether vertex' values are equal
            return true;
        }

            //loop through all vertex that are neighbors of v1
        for (V neighbor : super.neighbors(v1)){ 
            if (!neighbor.visited ){ //if the neighbor is not visited before
                return isReachableHelper(neighbor, v2, path); //recursive call
            }
        }

        path.pop(); //no path was found
        return false;
    }
4

1 に答える 1

2

問題: あなたのforループでは、最初の未訪問の隣接ノードのみを展開し、すぐにその再帰呼び出しの値を返します。つまり、 の最初の隣人を経由するパスが見つからない場合はv1、他の隣人を見ずに「あきらめる」だけです。

代わりに、再帰呼び出しが を返すノードが見つかるまで、すべてtrueの隣接ノードを試す必要があります。この場合、パスが見つかったので、戻ることができtrueます。それ以外の場合、メソッドはパスから最後のノードを正しくポップして戻りますfalse(バックトラッキング)。

for (V neighbor : super.neighbors(v1)){ 
    if (!neighbor.visited ){ //if the neighbor is not visited before
        if (isReachableHelper(neighbor, v2, path)) { //recursive call
            return true; // we found a path!
        }
    }
}
于 2013-03-14T21:32:55.207 に答える