关于bfs的一点疑问

我有个疑问，请问大家知道对于bfs什么时候该在while loop里加for loop，什么时候该用一个新的queue来记录下一层search 吗，还是说这是可有可无的。比方说
while queue:
            cur=queue.popleft()

和
while queue:
            for _ in range(len(queue)):
                cur=queue.popleft()

while queue:
            next_queue=collections.deque()
            for _ in range(len(queue)):
                cur=queue.popleft()

BFS通常会在while循环里面加for循环，目的是层级处理。通常情况下这里是不需要新创建第二个Queue来承接下一层的。

1. while(!queue.isEmpty()){
   
2.     final int SIZE = queue.size();
   
3.     // 层级处理
   
4.     for(int i = 0; i < SIZE; ++i){
   
5.         
   
6.     }
   
7. }

复制代码

也有情况是不需要的，往往发生在不需要层级处理的时候(一下子想不起来什么题目了)。不需要层级处理指的是:只需要把Queue里面的nodes处理掉就好，究竟哪一层无所谓(既然没有层级的概念了，这可能也就不算是严格意义上的BFS了，可能更多侧重在使用Queue的先进先出的处理次序上)。
BFS在while里面再创建新的Queue，印象里只见到过一次，就是双向BFS的时候，典型的题目是Word Ladder i, ii。也是层级处理，但是起点和终点同时BFS(而不是只由一个点出发)。不过Word Ladder i, ii使用的是Set，效果胜过Queue:remove/contains操作都是O(1)。

常规BFS用于处理edge weight相等的图(有向或者无向)。如果edge weight不相等，则需要用Djikstra's Algorithm, Bellman Ford, FloydWarshall等算法解决。


补充内容 (2020-9-2 04:59):
发现了一道在While里面创建Queue题目: LC358。原因是需要在层级里面集中处理多(k)个数据，可以使用list，但Queue会方便一些。

补充内容 (2020-9-5 05:05):
发现一道可以使用BFS解决但并不十分强调层级概念的题目LC572。
https://github.com/zea7ot/leetco ... onApproach0BFS.java

补充内容 (2020-9-6 01:53):
又发现一道BFS不强调是必须是层级处理的题目: LC404
https://github.com/zea7ot/leetco ... eetcode/lvl2/lc0404

queue里套for循环一般都是要对树里的每一层进行一些操作的，比如计算每层的和，没有for循环的话层与层之间就没有分界了。我还没刷到过queue里套queue的（也可能我忘了），你在哪一题里见过这样的呀？

如果你需要对同一层的结果进行处理的时候，里面就得再加个for loop。 比如说你要用bfs找最短路径之类的，同一层的节点距离是一样的，这样你就需要按每一层的结果来处理，这个时候就加一个for loop。

 看你在遍历完一层以后，还需不需要操作，比如算height，将这一层遍历的结果copy到数组里之类的。如果需要的话，要双重循环，否则，那么一个循环也可以。

zea7ot 发表于 2020-9-1 07:58
BFS通常会在while循环里面加for循环，目的是层级处理。通常情况下这里是不需要新创建第二个Queue来承接下一 ...

感谢层主回答，昨天在做web crawler这道题也发现用了第二个queue来承接，感觉还是不太理解，是因为这个新queue可以集中存处理后的url吗

Dido94 发表于 2020-9-4 07:05
感谢层主回答，昨天在做web crawler这道题也发现用了第二个queue来承接，感觉还是不太理解，是因为这个新 ...

你说的是LC1236吗?
如果是的话，这是我的解法，BFS的解法没有特别需要在while循环里创建队列的要求啊。

一般的BFS只有一个while就可以。
只有涉及到level order的travesal的时候，需要两层的loop。
至于用for还是while，就看个人爱好和语言，哪个写的漂亮就用哪个。
参考leetcode
https://leetcode.com/problems/word-ladder/
https://leetcode.com/problems/binary-tree-level-order-traversal/