LeetCode 785. Is Graph Bipartite?

题目描述

结果

知识点

图的遍历BFS+DFS、二分图

实现

码前思考

1. 这道题目是我专门找的二分图来做练习的，利用这道题回忆了一下二分图的概念！
2. 其实发现一个套路，当你去解决一道图的时候，发现没有思路，那么基本上 要往DFS或者BFS上面去靠 ，毕竟考点也就那么一些嘛~
3. 利用二分图的性质：相邻的两个点必须属于两个不同的集合，然后去遍历所有的边（注意是遍历所有的边，而不是所有的点！）。
4. 我们可以设计出类似于图着色的方式，对二分图进行着色！
5. 下面是LeetCode的官方题解思路，我的思路和它一样。
   1. 如果节点属于第一个集合，将其着为蓝色，否则着为红色。只有在二分图的情况下，可以使用贪心思想给图着色：一个节点为蓝色，说明它的所有邻接点为红色，它的邻接点的所有邻接点为蓝色，依此类推。
   2. 使用数组（或者哈希表）记录每个节点的颜色： color[node]。颜色可以是0，1，或者未着色（-1 或者 null）。
   3. 搜索节点时，需要考虑图是非连通的情况。 对每个未着色节点，从该节点开始深度优先搜索着色。每个邻接点都可以通过当前节点着相反的颜色。如果存在当前点和邻接点颜色相同，则着色失败。

代码实现

//记得考虑不是连通图的情况！

class Solution {
private:
    const static int maxn = 110;
    int id[maxn];
    bool flag;
public:
    bool isBipartite(vector<vector<int>>& graph) {
        fill(id,id+maxn,-1);
        flag = true;
        //采用深度优先搜索来判断是否是二分图,而且要考虑非连通图的情况
        for(int i=0;i<graph.size();i++){
            if(flag == false){
                break;
            }
            if(id[i] == -1){
                //进行深度优先搜索
                DFS(i,0,graph);
            }
        }

        return flag;
    }

    void DFS(int root,int setId,vector<vector<int>>& graph){
        if(flag == false){
            return;
        }else{
            //如果已经被标记过
            if(id[root] != -1){
                if(id[root] != setId){
                    flag = false;
                    return;
                }else{
                    return;
                }
            }
            //代表没有被标记
            id[root] = setId;
            printf("当前标记%d为%d\n",root,setId);
            for(int i=0;i<graph[root].size();i++){
                DFS(graph[root][i],1-setId,graph);
            }
        }
    }
};

码后反思

1. 这道题的核心就是要 遍历所有的边，而不是所有的点。 是在一般的DFS的模板上进行了一些修改的。