二分图

作者:sweetiee
链接:https://leetcode.cn/problems/is-graph-bipartite/solution/bfs-dfs-bing-cha-ji-san-chong-fang-fa-pan-duan-er-/
来源: 力扣 (LeetCode)
著作权归作者所有. 商业转载请联系作者获得授权, 非商业转载请注明出处.

什么是二分图

若无向图 $G=(V, E)$ 的顶点集 $V$ 可以分割为两个互不相交的子集, 且图中每条边的两个顶点分别属于不同的子集, 则称图 $G$ 为一个二分图.

判断二分图

深度优先搜索 / 广度优先搜索

我们使用图搜索算法从各个连通域的任一顶点开始遍历整个连通域, 遍历的过程中用两种不同的颜色对顶点进行染色, 相邻顶点染成相反的颜色. 这个过程中倘若发现相邻的顶点被染成了相同的颜色, 说明它不是二分图; 反之, 如果所有的连通域都染色成功, 说明它是二分图.

并查集

我们知道如果是二分图的话, 那么图中每个顶点的所有邻接点都应该属于同一集合, 且不与顶点处于同一集合. 因此我们可以使用并查集来解决这个问题, 我们遍历图中每个顶点, 将当前顶点的所有邻接点进行合并, 并判断这些邻接点中是否存在某一邻接点已经和当前顶点处于同一个集合中了, 若是, 则说明不是二分图.

具体实现

这几种方法都比较简单, 注释的很详细, 直接看注释就好啦～

广度优先搜索

class Solution {
    public boolean isBipartite(int[][] graph) {
        // 定义 visited 数组, 初始值为 0 表示未被访问,
        // 赋值为 1 或者 -1 表示两种不同的颜色.
        int[] visited = new int[graph.length];
        Queue<Integer> queue = new LinkedList<>();
        // 因为图中可能含有多个连通域, 所以我们需要判断是否存在顶点未被访问,
        // 若存在则从它开始再进行一轮 bfs 染色.
        for (int i = 0; i < graph.length; i++) {
            if (visited[i] != 0) {
                continue;
            }
            // 每出队一个顶点, 将其所有邻接点染成相反的颜色并入队.
            queue.offer(i);
            visited[i] = 1;
            while (! queue.isEmpty()) {
                int v = queue.poll();
                for (int w: graph[v]) {
                    // 如果当前顶点的某个邻接点已经被染过色了,
                    // 且颜色和当前顶点相同, 说明此无向图无法被正确染色, 返回 false.
                    if (visited[w] == visited[v]) {
                        return false;
                    }
                    if (visited[w] == 0) {
                        visited[w] = -visited[v];
                        queue.offer(w);
                    }
                }
            }
        }
        return true;
    }
}

深度优先搜索

class Solution {
    public boolean isBipartite(int[][] graph) {
        // 定义 visited 数组, 初始值为 0 表示未被访问,
        // 赋值为 1 或者 -1 表示两种不同的颜色. 
        int[] visited = new int[graph.length];
        // 因为图中可能含有多个连通域, 所以我们需要判断是否存在顶点未被访问,
        // 若存在则从它开始再进行一轮 dfs 染色.
        for (int i = 0; i < graph.length; i++) {
            if (visited[i] == 0 && ! dfs(graph, i, 1, visited)) {
                return false;
            }
        }
        return true;
    }

    private boolean dfs(int[][] graph, int v, int color, int[] visited) {
        // 如果要对某顶点染色时, 发现它已经被染色了,
        // 则判断它的颜色是否与本次要染的颜色相同,
        // 如果矛盾, 说明此无向图无法被正确染色, 返回 false.
        if (visited[v] != 0) {
            return visited[v] == color;
        }

        // 对当前顶点进行染色, 并将当前顶点的所有邻接点染成相反的颜色.
        visited[v] = color;
        for (int w: graph[v]) {
            if (! dfs(graph, w, -color, visited)) {
                return false;
            }
        }
        return true;
    }
}

并查集

class Solution {
    public boolean isBipartite(int[][] graph) {
        // 初始化并查集
        UnionFind uf = new UnionFind(graph.length);
        // 遍历每个顶点, 将当前顶点的所有邻接点进行合并
        for (int i = 0; i < graph.length; i++) {
            int[] adjs = graph[i];
            for (int w: adjs) {
                // 若某个邻接点与当前顶点已经在一个集合中了,
                // 说明不是二分图, 返回 false.
                if (uf.isConnected(i, w)) {
                    return false;
                }
                uf.union(adjs[0], w);
            }
        }
        return true;
    }
}

// 并查集
class UnionFind {
    int[] roots;
    public UnionFind(int n) {
        roots = new int[n]; 
        for (int i = 0; i < n; i++) {
            roots[i] = i;
        }
    }

    public int find(int i) {
        if (roots[i] == i) {
            return i;
        }
        return roots[i] = find(roots[i]);
    }

    // 判断 p 和 q 是否在同一个集合中
    public boolean isConnected(int p, int q) {
        return find(q) == find(p);
    }

    // 合并 p 和 q 到一个集合中
    public void union(int p, int q) {
        roots[find(p)] = find(q);
    }
}

复杂度分析

上述三种方法, 时间复杂度是 $O(N + M)$, 空间复杂度是 $O(N)$, 其中 $N$ 是无向图的顶点数, $M$ 是无向图的边数.

知识拓展导读

在二分图上, 最常见的问题是求二分图最大匹配/最大独立集. 二分图的最大匹配, 简单来说就是找到尽可能多的两两匹配的关系. 比如说在某场相亲现场, 主持人先让所有男生女生都写好自己感兴趣的若干个异性, 主持人需要尽可能多的凑一对对男女去约会.

这个问题经典的解法是匈牙利算法, 这块知识超过了面试要求, 感兴趣的同学可以自行查阅资料.

说到相亲, 还有一个著名的算法叫做稳定婚姻问题. 就是说, 主持人的你安排男男女女相亲, 如果当前是男 $1$ 和女 $2$ 在一起, 男 $2$ 和女 $1$ 在一起, 男 $1$ 更喜欢女 $1$, 女 $1$ 也更喜欢男 $1$, 那么他俩就会私奔, 你的安排相亲就是不稳定的. 对于一群男生和女生, 你需要给出一个稳定的相亲方案. 这个有趣的算法, 感兴趣的同学可以看下 matrix67 大神对于这个故事的阐述～

什么是算法: 如何寻找稳定的婚姻搭配