登录
  • #刷题

BF‌‌‍‍‌‍‍‌‍‌‍‍‌‌‌‍‍‍‍‌‌‌‌‌‍‍‌‍‌‌‍‍S什么时候可以忽略代表层序的for循环?

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

while(!q.empty()){[br][/br][br][/br]    int n=q.size();[br][/br][br][/br]    for(int i=0; i<n; i++){[br][/br][br][/br]        sth = q.front(); q.pop();[br][/br][br][/br]        for(auto neb : q.neighbors){[br][/br][br][/br]               q.push(neb);[br][/br][br][/br]        }[br][/br][br][/br]    }[br][/br][br][/br]}


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

里面的做法是

bool isBipartite(vector<vector<int>>& graph) {[br][/br][br][/br]        vector<int> colors(graph.size());[br][/br][br][/br]        for (int i = 0; i < graph.size(); ++i) {[br][/br][br][/br]            if (colors[i] != 0) continue;[br][/br][br][/br]            colors[i] = 1;[br][/br][br][/br]            queue<int> q{{i}};[br][/br][br][/br]            while (!q.empty()) {[br][/br][br][/br]                int t = q.front(); q.pop();[br][/br][br][/br]                for (auto a : graph[t]) {[br][/br][br][/br]                    if (colors[a] == colors[t]) return false;[br][/br][br][/br]                    if (colors[a] == 0) {[br][/br][br][/br]                        colors[a] = -1 * colors[t];[br][/br][br][/br]                        q.push(a);[br][/br][br][/br]                    }[br][/br][br][/br]                }[br][/br][br][/br]            }[br][/br][br][/br]        }[br][/br][br][/br]        return true;[br][/br][br][/br]    }[br][/br][br][/br]明显是没有用到管理层序的那个for循环啊!请哪位大侠指点一下为什么有些题目可以没有这个“层序for循环”,还有哪些情况是必须有的?谢谢啦[/i][/i]
5条回复
热度排序

发表回复