2

私は Java の初心者で、コードに問題があります。俳優から映画、俳優、映画、ケビン ベーコンへの最短パスを見つけたいと考えています。listこれは、 which に格納され"Actor A, Movie A, Actor B, Movie B, Kevin Bacon"ます。これを行う最善の方法は、それを行うことだと思いましたrecursively。しかし、私はStackOverflowError.

俳優と映画をHashMap<String, HashSet<String>>. _ 俳優と映画はどちらもkeys-俳優が呼び出された場合は、俳優が出演した映画の を返しHashSet、映画が呼び出された場合は、出演している俳優のを返します。このメソッドは、特定の俳優が共演したすべての俳優を見つけます。HashSetfindCostars

これが私のコードです。どんな助けでも大歓迎です！

public List<String> findBaconPath (String actor) throws IllegalArgumentException {
    ArrayList<String> actors = new ArrayList<String>();
    actors.add(actor);
    ArrayList<String> path = helper(actors, actor);
    return path;
}

public ArrayList<String> helper(ArrayList<String> curr, String actor) {
    ArrayList<String> list = new ArrayList<String>();
    HashSet<String> movies = myMovies.get(actor);
    ArrayList<String> coStars = (ArrayList<String>) findCostars(actor);
    Iterator<String> it = movies.iterator();
    while (it.hasNext()) {
        String next = it.next();
        HashSet<String> movAct = myMovies.get(next);
        if (movAct.contains("Bacon, Kevin")) {
            list.add("Bacon, Kevin");
            list.add(next);
            list.add(actor);
            return list;
        } else {
            Iterator<String> itAct = coStars.iterator();
            while(itAct.hasNext()) {
                curr.add(next);
                String nextActorValue = itAct.next();
                curr.add(nextActorValue);
                helper(curr, nextActorValue);
            }
        }
    }
    return null;
}
4

2 に答える 2

2

検索が深さ優先であり、既にアクセスしたグラフ ノードを除外していないため、スタック オーバーフローが発生しています。

おそらく最短経路が必要なので、Breadth-first search を実装してみてください。

于 2012-11-25T19:38:07.417 に答える
0

同じムービーを 2 回処理していないことを確認することはありません。

最初の呼び出しは処理を開始moviesし、最初の反復では最初のアクターと同じ映画に対して同じメソッドを呼び出す可能性があります。次に、2 番目の呼び出しでmovies....の反復が再び開始されます。

于 2012-11-25T19:31:34.160 に答える