首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >宽度优先搜索打印出凯文培根路径,重新访问节点?

宽度优先搜索打印出凯文培根路径,重新访问节点?
EN

Stack Overflow用户
提问于 2012-11-26 21:15:07
回答 1查看 1.4K关注 0票数 0

在我的程序中实现广度优先搜索时,我遇到了一些困难,该程序试图找到凯文·培根的号码。我已经创建了一个临时哈希集来存储已访问的节点,但是尽管我从返回到队列的列表中删除了节点,程序仍然继续重新访问节点。

演员和电影的信息存储在一个HashMap(String,HashSet(String))中--所以如果你把一个演员作为一个键,你会得到他们扮演的电影,如果你把一部电影作为密钥,你就会得到在其中扮演过角色的演员。下面是我的代码和System.out.prints打印的内容。谢谢你的帮助!

代码语言:javascript
运行
复制
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后移除中的内容。B、C
  • 这是访问的内容: D,A,电影7,电影2
  • 这就是coStars预删除中的内容。E,A,B
  • 这就是coStars后移除中的内容。E,B
  • 这是访问的内容: D,A,电影7,电影2,电影1
  • 这就是coStars预删除中的内容。A、B、C
  • 这就是coStars后移除中的内容。B、C
  • D,电影7,D,电影2,A,7,A,电影2,A,电影1,A,电影0,培根,凯文
EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2012-11-26 22:30:48

如果你能更好地区分参访名单中的电影和演员,而不是把它们混在一起,这可能会有所帮助。类似于:

代码语言:javascript
运行
复制
[(Movie1, Actor1, Actor2), (Movie2, Actor1, Actor2, Actor3)]

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

而且,每个循环都要调用两次removeAll。一次就在'if‘(coStars.contains("Bacon,Kevin“)之前){’,再一次就在您打印'post removal.‘’之前。

顺便问一下,这就是答案吗?电影7,电影2,电影1,电影0

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/13573274

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档