0

我在尝试查找 Kevin Bacon 号码的程序中实施广度优先搜索时遇到了一些麻烦。我创建了一个临时哈希集来存储访问过的节点，但是尽管我从反馈到队列中的列表中删除了节点，但程序仍在重新访问节点。

演员和电影的信息存储在 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，电影 7]
  • 这就是 coStars 预移除的内容。[D、A、B、C]
  • 这就是 coStars 删除后的内容。[A、B、C]
  • 这是访问的内容：[D，电影 7，电影 2]
  • 这就是 coStars 预移除的内容。[D、E、A、B]
  • 这就是 coStars 删除后的内容。[E、A、B]
  • 这是访问的内容：[D，A，电影 7，电影 2]
  • 这就是 coStars 预移除的内容。[A、B、C]
  • 这就是 coStars 删除后的内容。[乙，丙]
  • 这是访问的内容：[D，A，电影 7，电影 2]
  • 这就是 coStars 预移除的内容。[E、A、B]
  • 这就是 coStars 删除后的内容。[E, B]
  • 这是访问的内容：[D，A，电影 7，电影 2，电影 1]
  • 这就是 coStars 预移除的内容。[A、B、C]
  • 这就是 coStars 删除后的内容。[乙，丙]
  • [D，电影 7，D，电影 2，A，电影 7，A，电影 2，A，电影 1，A，电影 0，培根，凯文]
4

1 回答 1

0

如果您更好地区分访问列表中的电影和演员而不是混合它们，这可能会有所帮助。就像是：

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

然后，当您执行 removeAll 时，您始终可以按电影标题识别“已访问”中的条目。

此外，每个循环都会调用 removeAll 两次。在 'if (coStars.contains("Bacon, Kevin")){' 之前一次，在您打印 'post删除' 之前再一次。

顺便说一句，这是答案吗？电影 7、电影 2、电影 1、电影 0

于 2012-11-26T22:30:48.550 回答