0

ケビン・ベーコン数を見つけようとするプログラムに幅優先検索を実装する際に問題があります。訪問したノードを格納する一時的なハッシュセットを作成しましたが、キューにフィードバックするリストからノードを削除しても、プログラムはノードを再訪問し続けます。

俳優と映画の情報は HashMap(String, HashSet(String)) に保存されます。したがって、俳優をキーとして配置すると、その俳優が出演した映画が取得され、映画をキーとして配置すると、その中で演じた俳優を取得します。以下に私のコードと System.out.prints が出力するものを添付します。助けてくれてありがとう！

public List<String> findBaconPath (String actor) throws IllegalArgumentException {
    ArrayList<String> list = new ArrayList<String>();
    HashSet<String> visited = new HashSet<String>();
    visited.add(actor);
    LinkedList<String> bfs = new LinkedList<String>();
    bfs.add(actor);
    while (!bfs.isEmpty()){
        String curr = bfs.remove(); //The current actor we are looking at.
        visited.add(curr);
        HashSet<String> mov = myMovies.get(curr);
        Iterator<String> it = mov.iterator();
        while (it.hasNext()){
            String next = it.next(); //The next movie in the iterator.
            visited.add(next);
            HashSet<String> coStars = myMovies.get(next);
            coStars.removeAll(visited);
            if (coStars.contains("Bacon, Kevin")){
                list.add(curr);
                list.add(next);
                list.add("Bacon, Kevin");
                System.out.println(list.toString());
                return list;
            }
            else {
                list.add(curr);
                list.add(next);
                System.out.println("This is what is in visited: "+visited.toString());
                System.out.println("This is what is in coStars pre removal. "+ coStars.toString());
                coStars.removeAll(visited);
                System.out.println("This is what is in coStars post removal. "+ coStars.toString());
                Iterator<String> cos = coStars.iterator();
                while (cos.hasNext()){
                    bfs.add(cos.next());
                }
            }
        }

    }
    return list;
}
  • これは訪問したものです: [D, Movie 7]
  • これはcoStars pre removeにあるものです。[D、A、B、C]
  • これは、coStars ポスト削除に含まれるものです。[A、B、C]
  • これは訪問したものです: [D, Movie 7, Movie 2]
  • これはcoStars pre removeにあるものです。[D、E、A、B]
  • これは、coStars ポスト削除に含まれるものです。[え、あ、え]
  • これは訪問したものです: [D, A, Movie 7, Movie 2]
  • これはcoStars pre removeにあるものです。[A、B、C]
  • これは、coStars ポスト削除に含まれるものです。[B、C]
  • これは訪問したものです: [D, A, Movie 7, Movie 2]
  • これはcoStars pre removeにあるものです。[え、あ、え]
  • これは、coStars ポスト削除に含まれるものです。[え、べ]
  • これは訪問したものです: [D, A, Movie 7, Movie 2, Movie 1]
  • これはcoStars pre removeにあるものです。[A、B、C]
  • これは、coStars ポスト削除に含まれるものです。[B、C]
  • [D、ムービー 7、D、ムービー 2、A、ムービー 7、A、ムービー 2、A、ムービー 1、A、ムービー 0、ベーコン、ケビン]
4

1 に答える 1

0

訪問したリストで映画と俳優を混在させるのではなく、よりよく区別すると役立つ場合があります。何かのようなもの：

[(Movie1, Actor1, Actor2), (Movie2, Actor1, Actor2, Actor3)]

次に、removeAll を実行すると、映画のタイトルで「visited」のエントリをいつでも識別できます。

また、removeAll はループごとに 2 回呼び出されます。「if (coStars.contains("Bacon, Kevin")){」の直前と、「削除後」を印刷する直前にもう一度。

ところで、これが答えですか？動画 7、動画 2、動画 1、動画 0

于 2012-11-26T22:30:48.550 に答える