我对 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;
}
最佳答案
您会出现堆栈溢出,因为您的搜索是深度优先的,并且您没有排除已经访问过的图形节点。
由于您可能想要最短路径,请尝试实现 Breadth-first search .
关于java - Java 中的 Kevin Bacon 路径出现堆栈溢出?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13554592/