一起学习交流~

二分图-DFS+BFS+UnionFind

算法 laomuji 7个月前 (03-06) 430次浏览 已收录 0个评论

判断二分图

链接:https://leetcode-cn.com/problems/is-graph-bipartite/

DFS/BFS

思路

如果这个无向图是一个连通图
那么
从其中一个节点出发,从所有的边递归,可以递归访问所有的节点

二分图 要求每个边的两个端点不能处于同一个集合
假设 第一个节点处于A ,那么第二个节点必须处于节点B
可以假设上色的方式,采用红黑交替染色的方式
dfs的方式:
假设从节点0出发,默认先染色红色

[[1,2,3],[0,2],[0,1,3],[0,2]]
初始颜色: 红 无 无 无
0通往1 2 3,0为红,对应的边的点染色为黑色,颜色:红 黑 黑 黑
1通往0 2,1为黑,对应的边的点边染色为红色,0为红与想染的颜色相同,不需要再递归,2为黑,与想染的颜色不同,冲突返回false

[[1,3],[0,2],[1,3],[0,2]]
初始颜色: 红 无 无 无
0通往1 3,0为红,对应的边的点染色为黑色,颜色:红 黑 无 黑
1通往0 2,1为黑,对应的边的点染色为红色,0为红与想染的颜色相同,不需要递归,颜色:红 黑 红 黑
2通往1 3,2为红,对应的边的点染色为黑色,1 3为红与想染的颜色相同,不需要递归,颜色:红 黑 红 黑
2通往1 3,2为红,对应的边的点染色为黑色,1 3为红与想染的颜色相同,不需要递归,颜色:红 黑 红 黑
3通往0 2,3为黑,对应的边的点染色为红色,0 2为红与想染的颜色相同,不需要递归,颜色:红 黑 红 黑

因为这个图可能不是连通图,在不是连通图的情况下,无法一次访问所有的节点
所以 所以 没有颜色的节点就是没有访问过的节点,需要开始搜索

bfs的方式:
思路基本一样,不过多赘述

代码

dfs

class Solution {
private:
    enum COLOR{NOCOLOR,RED,BLACK};
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int size = graph.size();
        vector<COLOR>colors(size,COLOR::NOCOLOR);
        for(int i =0;i<size;i++){
            if(colors[i]==COLOR::NOCOLOR && dfs(graph,colors,i,COLOR::RED)==false)return false;
        }
        return true;
    }
    //当颜色冲突时返回false
    bool dfs(vector<vector<int>>& graph,vector<COLOR>&colors,int index,COLOR color){
        //如果没有颜色,那么需要判断颜色是否冲突
        if(colors[index]!=COLOR::NOCOLOR)return colors[index]==color;

        colors[index]=color;//染色

        //红色变黑 黑色变红
        color = color==COLOR::BLACK ? COLOR::RED : COLOR::BLACK;

        //通过边开始递归
        for(int i =0;i<graph[index].size();i++){
            if(dfs(graph,colors,graph[index][i],color)==false)return false;
        }

        return true;
    }
};

bfs

class Solution {

private:
    enum COLOR{NOCOLOR,RED,BLACK};
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int size = graph.size();
        vector<COLOR>colors(size,COLOR::NOCOLOR);
        for(int i =0;i<size;i++){
            if(colors[i]!=COLOR::NOCOLOR )continue;
            colors[i]=COLOR::RED;//给当前节点染色
            queue<int>que;
            que.push(i);
            while(que.size()){
                int u = que.front();que.pop();
                for(int j=0;j<graph[u].size();j++){
                    int v = graph[u][j];
                    if(colors[v]==colors[u])return false;//如果要染的颜色和当前颜色相同,则表示冲突
                    if(colors[v]!=COLOR::NOCOLOR)continue;//如果颜色不冲突且已经染色了,不需要循环
                    colors[v] = colors[u]==COLOR::BLACK?COLOR::RED : COLOR::BLACK;//取相反的颜色染色
                    que.push(v);
                }
            }

        }
        return true;
    }

};

并查集

思路

并查集
这个比较难理解 之前并查集是合并当前节点 这个题用并查集是合并对方的节点
也就是说
当前节点处于一个集合,当前节点的邻接点全部属于另一个集合
也就是说 判断当前点 是否和邻接点是同一个集合,
如果属于,那就冲突
如果不属于,那么应该把邻接点进行合并

代码

class Solution {
private:
    class UnionFind{
        public:
        vector<int>root;
        UnionFind(int n){
            root.resize(n);
            for(int i =0;i<n;i++)root[i]=i;
        }

        int find(int x){
            if(x==root[x])return x;
            root[x]=find(root[x]);
            return root[x];
        }

        void unionXY(int x,int y){
            int rootX = find(x);
            int rootY = find(y);
            if(rootX!=rootY)root[rootX]=rootY;
        }

        bool isConnect(int x,int y){
            return find(x)==find(y);
        }
    };
public:
    bool isBipartite(vector<vector<int>>& graph) {
        UnionFind uf(graph.size());
        for(int i =0;i<graph.size();i++){
            for(int j =0;j<graph[i].size();j++){
               if(uf.isConnect(i, graph[i][j]))return false;
               //将附近的点相连,但不能与当前点相连,因为不能处于同一个集合
               uf.unionXY(graph[i][0], graph[i][j]);
            }
        }
        return true;
    }

};

效率

都是o(n+m),边数+点数

可能的二分法

链接 https://leetcode-cn.com/problems/possible-bipartition/

DFS/BFS

题解

与上面一个题基本一样,只不过需要手动建图而已
定义三种情况
1 未分组
2 A组
3 B组
首先是未分组,可以随意分组
如果已经分组了 且和想要分的组不同 表示冲突 返回false

代码

class Solution {
private:
enum GROUP{NOGROUP,AGROUP,BGROUP};
public:
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        n++;
        vector<vector<int>>edges(n,vector<int>());
        for(const auto&dislike:dislikes){
            edges[dislike[0]].push_back(dislike[1]);
            edges[dislike[1]].push_back(dislike[0]);
        }
        vector<GROUP>groups(n,GROUP::NOGROUP);
        for(int i =0;i<n;i++){
            if(groups[i]== GROUP::NOGROUP && dfs(edges,groups,i,GROUP::AGROUP)==false)return false;
        }
        return true;
    }
    bool dfs(vector<vector<int>>&edges,vector<GROUP>&groups,int index,GROUP group){
        //如果已经分组,那么返回想分组和已分组是否冲突
        if(groups[index] != GROUP::NOGROUP)return groups[index] == group;
        //如果未分组,进行分组
        groups[index] = group;
        //取相反的分组
        group = group == GROUP::BGROUP ? GROUP::AGROUP : GROUP::BGROUP;
        //将与当前点连接的点分组修改
        for(int i =0;i<edges[index].size();i++){
            //若分组冲突则返回false
            if(dfs(edges,groups,edges[index][i],group)==false)return false;
        }
        return true;
    }
};
class Solution {
private:
enum GROUP{NOGROUP,AGROUP,BGROUP};
public:
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        n++;
        vector<vector<int>>edges(n,vector<int>());
        for(const auto&dislike:dislikes){
            edges[dislike[0]].push_back(dislike[1]);
            edges[dislike[1]].push_back(dislike[0]);
        }
        vector<GROUP>groups(n,GROUP::NOGROUP);
        for(int i =0;i<n;i++){
            if(groups[i]==NOGROUP){
                groups[i]=GROUP::AGROUP;//默认先放到A组
                queue<int>que;
                que.push(i);
                while(que.size()){
                    int u = que.front();que.pop();
                    GROUP group = groups[u]==GROUP::BGROUP ? GROUP::AGROUP : GROUP::BGROUP;//取相反的组
                    for(int j =0;j<edges[u].size();j++){
                        int v = edges[u][j];
                        if(groups[v]==group)continue;//如果需要分的组相同,不需要操作
                        if(groups[v]!=GROUP::NOGROUP)return false;//如果分组不同且已经分组了那么表示冲突
                        groups[v]=group;//如果没有分组 进行分组
                        que.push(v);//加入队列
                    }
                }
            }
        }
        return true;
    }

};

效率

喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论