java - Java 中的 Kevin Bacon 路径给出了堆栈溢出？

Question

我是 Java 的新手，我的代码有问题，我想找到从 Actor 到电影到 Actor 到电影再到 Kevin Bacon 的最短路径。这存储在 list 中哪个会去"Actor A, Movie A, Actor B, Movie B, Kevin Bacon" .我认为最好的方法就是这样做 recursively .但是，我得到一个 StackOverflowError .

我将 Actor 和电影 存储在HashMap<String, HashSet<String>> 中. Actor 和电影都是keys - 如果 actor 被调用，那么它返回一个 HashSet Actor 参演过的电影，如果调用电影，它会返回一个HashSet。它拥有的 Actor 。 findCostars方法查找给定 Actor 与之合作过的所有 Actor 。

这是我的代码。任何帮助将不胜感激!

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

Answer 1

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

因为您可能想要最短路径，请尝试实现 Breadth-first search .