bfs时到底什么情况下要加一层size for

如题一直很蒙蔽
  有的题，bfs遍历
    弹出一个点
     就开始处理newX, newY
  有的题
需要  加一层 当前q的size的loop
   while(q不为空){
       for(int i=0;i<q.size();i++){
             当前元素=q.poll()
              //newX, newY
        }
   }

我的 问题是：
   有什么规律可以follow: 啥时候要加 ，啥时候不加 这个
for(int i=0;i<q.size();i++)

bfs是层层推进的，当你需要知道你进行到哪一层的时候，就要取size。有些时候可以把层数作为一个变量定义在queue的元素里面，可以避开size。

只要你想知道啥时候一行结束，都要加啊，不然当前行的孩子也进queue了，你poll出来那个孩子的时候并不知道已经是下一行了

当你处理每一个node的时候需要知道它属于哪一层（到src距离相等的为一层）， 要用这个q.size()构建forloop
可以看下把binary tree变成List<List<>> 那道题。

banffcloud 发表于 2021-5-31 02:40
当你处理每一个node的时候需要知道它属于哪一层（到src距离相等的为一层）， 要用这个q.size()构建forloop
...

yes 这正是答案

bfs 可以处理“最短距离”，“最小次数”，这一类题目，在这一类题目中，我们每多走一步，队列会push pop多次，这里就需要用到楼主说的。像拓扑排序，树的bfs 之类的 是不需要的。

stanlin6666 发表于 2021-5-31 10:13
bfs 可以处理“最短距离”，“最小次数”，这一类题目，在这一类题目中，我们每多走一步，队列会push pop多 ...

满分回答

用Java刷时候发现必须先写一个int n =q.size()然后再loop，否则出错，不知道为什么

RELAY2014 发表于 2021-6-11 11:45
用Java刷时候发现必须先写一个int n =q.size()然后再loop，否则出错，不知道为什么

因为你在loop中通常会push新的node上去，每次check loop condition的时候size就变了…所以要用一个variable先存下来

short answer：当题目要求知道层数的时候（到起点的距离）会需要这个loop
ps：是不是不应该直接用q.size在for loop，应该先存一下q.size再用吧，不然for中操作会改变q.size