Leetcode-785-判断二分图

发表于 | 分类于

题目

给定一个无向图graph，当这个图为二分图时返回true。

如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。

graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。

image-20200716102844735

注意:

graph 的长度范围为 [1, 100]。
graph[i] 中的元素的范围为 [0, graph.length - 1]。
graph[i] 不会包含 i 或者有重复的值。
图是无向的: 如果j 在 graph[i]里边, 那么 i 也会在 graph[j]里边。

思路

对图中的节点进行染色. 以任意一个节点开始, 将其染成红色, 然后对图进行遍历, 将其邻居染成黑色. 然后将黑色的邻居染成红色. 如果可以染色成功, 说明这个图是二分图, 两个集合分别是黑色节点和红色节点. 如果染色不能成功, 说明该图不是二分图.

遍历图的思路主要有两种, 分别是深度优先搜索DFS和广度优先搜索BFS.

深度优先搜索DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    // 染色的标记
    private static int UNCOLOR = 0;
    private static int RED = 1;
    private static int BLACK = 2;

    // 标记节点是否染色
    private int[] colorFlag;

    // 是否符合题目要求
    boolean valid = true;

    public boolean isBipartite(int[][] graph) {
        colorFlag = new int[graph.length];
        for (int i = 0; i < graph.length; i++) {
            // 因为图不一定是连通的, 所以需要以所有为染色的节点为起点去染色
            if (colorFlag[i] == UNCOLOR) {
                dfs(i, RED, graph);
            }
        }
        return valid;
    }

    private void dfs(int node, int color, int[][] graph) {
        // 对当前节点进行染色
        colorFlag[node] = color;
        // 确定相邻节点需要染的颜色
        int colorOfNeighbour = color == RED? BLACK: RED;
        // 遍历相邻的节点
        for (int neighbour: graph[node]) {
            if (colorFlag[neighbour] == UNCOLOR) {
                dfs(neighbour, colorOfNeighbour, graph);
                // 通过上面的dfs, 如果不是二分图, 则直接返回
                if (!valid) {
                    return;
                }
            } else if (colorFlag[neighbour] != colorOfNeighbour) {
                // 如果相邻节点已经有颜色, 而且和确定要染的颜色不一样的话, 则说明不是二分图
                // 不满足题目要求
                valid = false;
                return;
            }
        }
    }
}

image-20200716103505511

广度优先搜索BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    // 染色的标记
    private static int UNCOLOR = 0;
    private static int RED = 1;
    private static int BLACK = 2;

    // 标记节点是否染色
    private int[] colorFlag;

    public boolean isBipartite(int[][] graph) {
        colorFlag = new int[graph.length];
        for (int i = 0; i < graph.length; i++) {
            // 因为图不一定是连通的, 所以需要以所有为染色的节点为起点去染色
            if (colorFlag[i] == UNCOLOR) {
                Queue<Integer> queue = new LinkedList<>();
                // 先将第一个节点入队
                queue.offer(i);
                colorFlag[i] = RED;
                while (!queue.isEmpty()) {
                    // 队首节点出队
                    int node = queue.poll();
                    // 确认出队节点的相邻节点需要染的颜色
                    int colorOfNeighbour = colorFlag[node] == RED? BLACK: RED;
                    // 遍历出队节点的所有相邻节点
                    for (int neighbour: graph[node]) {
                        if (colorFlag[neighbour] == UNCOLOR) {
                            // 如果当前相邻节点还没有染色
                            // 入队
                            queue.offer(neighbour);
                            // 染色
                            colorFlag[neighbour] = colorOfNeighbour;
                        } else if (colorFlag[neighbour] != colorOfNeighbour) {
                            // 如果当前相邻节点已染色, 且与需要染的颜色不一样
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    } 
}

image-20200716105628992