2

我对 Java 很陌生，我的代码中有一个问题，我想找到从演员到电影到演员到电影到 Kevin Bacon的最短路径。这存储在一个listwhich would go"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

您会遇到堆栈溢出，因为您的搜索是深度优先的，并且您没有排除您已经访问过的图形节点。

由于您可能想要最短路径，请尝试实施广度优先搜索。

于 2012-11-25T19:38:07.417 回答
0

您永远不会检查您是否两次处理同一部电影。

第一次调用将开始处理movies，第一次迭代可能会为第一个演员和相同的电影调用相同的方法。然后第二次调用将再次开始迭代movies......

于 2012-11-25T19:31:34.160 回答