二分图

• 二分图：一个无向图，可以划分为两个集合，且集合的内部不存在连接两个顶点的边
• 图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻
• 一个图是二分图当且仅当这个无向图不含有奇数环(没有奇数条边的环)

判定：染色法

• 时间复杂度：$O(n+m)$

• 题目模板参考：LeetCode785.判断二分图

• 如果染色的过程中没有出现矛盾，则该图为二分图

1.DFS

伪代码

//保证所有连通块中的点都被染色
for(int i = 0; i < n; i++){
    if(i未被染色){
        dfs(i, 1)
    }
}
c=1为一个颜色，c=2为另一个颜色，可以由3-1或者3-2来控制相邻点的颜色
boolean dfs(int u, int c){
    color[u] = c;//染色
    for(u的所有出边){
        if(相邻点未染色) dfs(相邻点,3-c)
        else if(相邻点与本节点同色) 出现矛盾，不是二分图
    }
}

Java代码

class Solution {
    int[] color;
    int[][] graph;
    public boolean isBipartite(int[][] _graph) {
        graph = _graph;
        int n = graph.length;
        color = new int[n];
        for(int i = 0; i < n; i++){
            if(color[i] == 0) {
                if(!dfs(i, 1)) return false;
            }
        }
        return true;
    }

    boolean dfs(int u, int c){
        color[u] = c;
        if(graph[u].length == 0) return true;
        for(int ver: graph[u]){
            if(color[ver] == 0){
                if(!dfs(ver, 3-c)) return false;
            }else if(color[ver] == c) return false;
        }
        return true;
    }
}

2.BFS

伪代码

for(int i = 0; i < n; i++){
    if(i未染色){
        i染色，并且入队
        while(队列非空){
            取出队头元素t
            用t来染出边的点
                1.如果相邻点未染色，则染成与t不同的颜色，并入队
                2.如果相邻点与同色，则染色失败，不是二分图
        }
    }
}
队列中维护的是刚刚被染色，准备去染其他出边的点

Java代码

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < n; i++){
            if(color[i] == 0) {
                color[i] = 1;
                q.offer(i);
                while(q.size() != 0){
                    int t = q.poll();
                    for(int ver: graph[t]){
                        if(color[ver] == 0){
                            color[ver] = 3 - color[t];
                            q.offer(ver);
                        }else if(color[ver] == color[t]) return false;
                    }
                }
            }
        }
        return true;
    }
}