BFS什么时候可以忽略代表层序的for循环？

我理解无论是树还是图，做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.     }
    
20. 
    

复制代码

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

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

复制代码

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

需要最短路就把for 循环加上。只是普通遍历就无所谓

需要知道是第几层的时候就要呀，反之不用

完全不需要第一层for loop，去掉它访问顺序也不变

其实如果楼主想有一套模板的话，就不要for循环，需要level的时候往queue里面把每个node的level也加上去，这样不需要for循环也能拿到距离了