查看: 870|回复: 5
收起左侧

[Leetcode] BFS什么时候可以忽略代表层序的for循环?

|只看干货
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (13)
 
 
0% (0)    👎

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

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

x
我理解无论是树还是图,做BFS的典型模板应该是这个样子:

  1. while(!q.empty()){
  2.     int n=q.size();
  3.     for(int i=0; i<n; i++){
  4.         sth = q.front(); q.pop();
  5.         for(auto neb : q.neighbors){
  6.                q.push(neb);
  7.         }
  8.     }
  9. }
复制代码

我是初学者,理解得不是很透,感觉外面的那层for循环代表了BFS的一层。但是我看了一些leetcode的答案,明确说是用BFS来做,但是这一层for循环被忽略掉了,这让我很不解。比如LC 785 题Is Biparticle Graph? https://www.cnblogs.com/grandyang/p/8519566.html
里面的做法是

  1. bool isBipartite(vector<vector<int>>& graph) {
  2.         vector<int> colors(graph.size());
  3.         for (int i = 0; i < graph.size(); ++i) {
  4.             if (colors[i] != 0) continue;
  5.             colors[i] = 1;
  6.             queue<int> q{{i}};
  7.             while (!q.empty()) {
  8.                 int t = q.front(); q.pop();
  9.                 for (auto a : graph[t]) {
  10.                     if (colors[a] == colors[t]) return false;
  11.                     if (colors[a] == 0) {
  12.                         colors[a] = -1 * colors[t];
  13.                         q.push(a);
  14.                     }
  15.                 }
  16.             }
  17.         }
  18.         return true;
  19.     }

复制代码
明显是没有用到管理层序的那个for循环啊!请哪位大侠指点一下为什么有些题目可以没有这个“层序for循环”,还有哪些情况是必须有的?谢谢啦

评分

参与人数 1大米 +5 收起 理由
14417335 + 5

查看全部评分


上一篇:微软近期高频面试题分享 + 分析(十二)
下一篇:【排序】常用的有几种?
timzyt 2021-8-12 14:13:07 | 显示全部楼层
本楼: 👍   100% (3)
 
 
0% (0)   👎
全局: 👍   100% (122)
 
 
0% (0)    👎
本帖最后由 timzyt 于 2021-8-11 23:15 编辑
  1. while(!q.empty()){
  2.     int n=q.size();
  3.     for(int i=0; i<n; i++){
  4.         sth = q.front(); q.pop();
  5.         for(auto neb : q.neighbors){
  6.                q.push(neb);
  7.         }
  8.     }
  9. }
复制代码


楼主您好,以您的这段BFS模板为例。

while中for循环的核心目的是为了给搜索的节点分层。

如果去掉for循环,那这个模板就是普通的BFS搜索,保证图中每个节点和边都被搜索一次,且每个点都是通过最短路径(from root)被找到。(这是BFS的基本性质)
但是,我们并不知道,每个点到root的最短路径是多少。

但是加上这个for循环可以让我们知道,每个点的最短路径(from root)是几。

只需要在代码模板中做一点小小的修改


  1. int minPathCount = 0;
  2. while(!q.empty()){
  3.     int n=q.size();
  4.     for(int i=0; i<n; i++){
  5.         sth = q.front(); q.pop();
  6.         std::cout << "Min path from root to node: " << sth << " is " << minPathCount << "\n";
  7.         for(auto neb : q.neighbors){
  8.                q.push(neb);
  9.         }
  10.     }
  11.     minPathCount ++;
  12. }
复制代码


那么啥时候需要知道最短路径的值呢?举个例子,如果是Numbers of Island,我们只需要运用BFS的“每个节点访问一次”的性质。那我们就不需要给节点分层,也就不需要中间这个for loop。但是如果题目是Word Ladder,那么你需要知道最短距离是几,你就需要用这个带for loop的模板。

评分

参与人数 3大米 +5 收起 理由
aaron_lam + 3 赞一个!
ttxs2016 + 1 很有用的信息!
liszt + 1 赞一个

查看全部评分

回复

使用道具 举报

TQL0200 2021-8-12 14:35:42 来自APP | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   83% (2878)
 
 
16% (583)    👎
需要最短路就把for 循环加上。只是普通遍历就无所谓

评分

参与人数 2大米 +2 收起 理由
ttxs2016 + 1 给你点个赞!
liszt + 1 赞一个

查看全部评分

回复

使用道具 举报

YCCHANG 2021-8-3 23:16:33 | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   93% (1607)
 
 
6% (120)    👎
需要知道是第几层的时候就要呀,反之不用

评分

参与人数 2大米 +2 收起 理由
ttxs2016 + 1 很有用的信息!
14417335 + 1

查看全部评分

回复

使用道具 举报

Mint92 2021-8-3 22:18:20 来自APP | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (21)
 
 
0% (0)    👎
完全不需要第一层for loop,去掉它访问顺序也不变

评分

参与人数 2大米 +2 收起 理由
ttxs2016 + 1 很有用的信息!
14417335 + 1

查看全部评分

回复

使用道具 举报

ZhangFan 2021-8-12 16:34:01 来自APP | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   98% (143)
 
 
1% (2)    👎
其实如果楼主想有一套模板的话,就不要for循环,需要level的时候往queue里面把每个node的level也加上去,这样不需要for循环也能拿到距离了

评分

参与人数 1大米 +1 收起 理由
ttxs2016 + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

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

本版积分规则

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