Leetcode--Java--785. 判断二分图

染色法 （DFS + 递归 / BFS ）
一个图是二分图等价于图可以被二染色等价于图中不含有奇数环

染色法的思路：

图的存储最常用是链式前向星，参考这里，本题就用二维数组存储图即可

dfs + 递归思想

class Solution {
    int g[][];
    int vis[];
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        g = graph;
        vis = new int[n]; //0表示未染色，1和-1表示两种颜色
        for (int i = 0; i < n; i ++ ) {
                //没有染色就进行染色，失败就直接false
                if (vis[i] == 0 && !dfs(i, 1)) {
                    return false;
                }
        }
        return true;
    }
    public boolean dfs(int u, int color) {
        //如果已经染过色，对比是否一样   不一样就矛盾
        if (vis[u] != 0) {
            return vis[u] == color;
        }
        vis[u] = color;
        for (int vtx: g[u]) {
            //将所有相邻的结点染成不同的颜色
            if (!dfs(vtx, -color)) {
                return false;
            }
        }
        return true;
    }
}

BFS

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int vis[] = new int[n];
        Deque q = new linkedList<>();
        //由于可能有多个连通域，要遍历每个结点
        for (int i = 0; i < n; i ++ ) {
            //如果顶点访问过
            if (vis[i] != 0) {
                continue;
            }
            q.offer(i);
            vis[i] = 1;
            while (!q.isEmpty()) {
                int node = q.poll();
                //遍历所有的邻结点
                for (int v: graph[node]) {
                    //颜色一样就false
                    if (vis[v] == vis[node]) {
                        return false;
                    }
                    //染相反的颜色，然后入队
                    if (vis[v] == 0) {
                        vis[v] = -vis[node];
                        q.offer(v);
                    }
                }
            }
        }
        return true;
    }
}