📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 2031| 回复: 1
跳转到指定楼层
上一主题 下一主题
收起左侧

[Leetcode] BFS类型的一点感想

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本帖最后由 blue_epoch 于 2019-9-23 12:01 编辑

最近做了很多BFS的题,感觉主要要注意两个方面。

一个方面是类型选择。普通的Queue或是PriorityQueue. 如果有比较路径大小(寻找最短路径)用PriorityQueue,而且往往使用PriorityQueue<int[]>,比如<距离,到达点>。

另一个方面是什么时候加visited。为了防止进入无限循环,我们往往要加一个visited,它可以是数组或set,用来记录不想要再次访问的节点。这里有三种情况。

一种是一旦访问过就【不想要再次访问】,这种最常见,比如200 number of islands 或是785 is graph bipartite. 这种情况在遍历邻居们或者poll元素的时候添加visited都可以。
第二种是当层访问过以后【不想要再次访问】,比如 126 Word Ladder II 。这里需要使用一个hashmap记录node的层数,只有当前层数等于map记录的层数的时(也就是还在当层)才可以添加。因为我们只要添加距离最短的路径。一旦之前层添加过了,就没必要在更后面的层添加了。这种情况不同于第三种,这里的距离只与层数有关,随着层数逐步加一。而第三种情况对于每条edge的距离都不一样,所有要poll了才知道那条最短。
第三种是得到(也就是poll之后) 【不想要再次访问】, 这种情况往往用在PriorityQueue最短路径问题上。比如743 network delay time,当节点从PriorityQueue中poll出来后,说明能够到达改节点的最短路径已经获得,之后就不要再访问该节点了。这里只需要在poll出元素后先check是否visited,如果没有,则添加visited并进行下一轮操作。这种情况节点在哪一层添加的不重要,重要的是距离。也许第一层就加进PriorityQueue了,奈何这条路径距离太长,它就不是我们想要的。

评分

参与人数 3大米 +8 收起 理由
winterfel1 + 1 赞一个
__q__ + 1 很有用的信息!
14417335 + 6

查看全部评分


上一篇:一个不错的画图的工具
下一篇:刷题-上瘾
🔗
dawannatie 2019-9-24 01:43:03 | 只看该作者
全局:
谢谢分享. 非常好的总结
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表