[数据结构与算法]判断二分图【bfs】

题目是判断二分图

给定一个可能不是连通的无向图，我们需要判断此图是不是一个二分图。
在一个连通的无向图内，判断二分图的方法为：

1. 初始化所有结点都未染色，染色数组color初始化全未0
2. 从任意一个结点开始，将其染为颜色1，并从该结点开始遍历整个图
3. 如果我们通过u结点和v结点之间的边遍历到了v结点

有以下两种情况：

• 如果v未被染色，那么我们将其染成于u不同的颜色，并从v继续往下遍历
• 如果v被染色，v的颜色如果于u相同的话，则说明不是一个二分图，返回false

当遍历结束的时候，返回true
由于题目给定的无向图不保证一定连通，因此我们需要进行多次遍历，直到每一个结点都被染色或者确定答案为false之后才能返回

bool isBipartite(vector<vector<int>>& graph) {
    int n=graph.size();
    vector<int>color(n,0);
    for(int i=0;i<n;i++){ //需要多次遍历直到所有结点被遍历
        if(color[i]==0){ //从一个没有被染色的结点开始
            queue<int>q;
            q.push(i);
            color[i]=1; //将其染色为颜色1
            while(!q.empty()){
                int cur=q.front();
                int c; //记录与cur相连的结点应该染的颜色
                if(color[cur]==1) c=2;
                else if(color[cur]==2) c=1;
                else c=0;
                q.pop();
                for(auto& g:graph[cur]){ //遍历与cur相连的结点
                    if(color[g]==0){ //如果未被染色
                        q.push(g); //加入队列
                        color[g]=c; //将其染色为c
                    }
                    else if(color[g]!=c) return false; //不是他应该的颜色直接返回false
                }
            }
        }
    }
    return true; //遍历完之后返回true
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖