【Leetcode】785.判断二分图

785 判断二分图

题目

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

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

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

示例 1:
输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释: 
无向图如下:
0----1
|    |
|    |
3----2
我们可以将节点分成两组: {0, 2} 和 {1, 3}。

示例 2:
输入: [[1,2,3], [0,2], [0,1,3], [0,2]]
输出: false
解释: 
无向图如下:
0----1
| \  |
|  \ |
3----2
我们不能将节点分割成两个独立的子集。

方法一（深度优先搜索）

对图进行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
int[] visited;
public boolean isBipartite(int[][] graph) {
    //visited数组记录一个节点有没有被染色，若为0则没被染色，若为-1或1则被染成相应的颜色
    visited = new int[graph.length];
    for(int i = 0; i < graph.length; i++){
        //如果一个节点没有被染色，并且从它出发不能成功地将图染成两种颜色，则返回false
        if(visited[i] == 0){
            if(!dfs(graph, i, 1))
                return false;
        }
    }
    return true;
}
//从将节点i染成颜色color开始，判断能否将图染成二分图
public boolean dfs(int[][] graph, int i, int color){
    //递归返回条件：如果一个节点已经染色了，判断这个节点的颜色和当前要给它染的颜色color是否相同
    if(visited[i] != 0)
        return visited[i] == color;
    //将当前节点染成color色，并将它的所有相邻节点染成-color色
    visited[i] = color;
    for(int j : graph[i]){
        //如果从i的一个相邻节点j开始，都没能成功地将图染成两种颜色，那么从i开始肯定也不行，返回false
        if(!dfs(graph, j, -color))
            return false;
    }
    return true;
}

方法二（广度优先遍历）

思路和方法一相同，只是遍历的方法从DFS改成了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
public boolean isBipartite(int[][] graph) {
    //visited数组记录一个节点有没有被染色，若为0则没被染色，若为-1或1则被染成相应的颜色
    int[] visited = new int[graph.length];
    //如果经过一遍BFS，尚且有节点未被染色，说明这个节点和刚才遍历到的节点不在一个连通图，要从这个节点开始再进行BFS
    for(int i = 0; i < graph.length; i++){
        if(visited[i] != 0)
            continue;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(i);
        visited[i] = 1;
        while(!queue.isEmpty()){
            int cur = queue.poll();
            for(int neighbor : graph[cur]){
                //如果相邻节点已经染色，并且和cur颜色一样，说明不是二分图，返回false
                if(visited[neighbor] == visited[cur])
                    return false;
                //如果有cur的相邻节点尚未染色，则将这个相邻节点染成和cur不同的颜色
                if(visited[neighbor] == 0){
                    visited[neighbor] = -visited[cur];
                    queue.add(neighbor);
                }
            }
        }
    }
    return true;
}

方法三（并查集）

在一个二分图中，一个节点的所有邻居都具有相同的颜色，并且和这个节点颜色不同。

因此我们如果用并查集来看这个问题，则上面一句话可以翻译如下：在二分图中，一个节点的所有邻居都在相同的集合中，并且和这个节点所在的集合不同。

我们可以遍历所有节点，当遍历到一个节点时，先判断它是否有邻居节点和它已经在一个集合中了(find)，如果有则不是二分图，直接返回false，否则将它的所有邻居节点所在的集合合并(union)，再接着遍历下一个节点。

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
    public boolean isBipartite(int[][] graph) {
        UnionFindSet ufs = new UnionFindSet();
        List<Integer> nodes = new LinkedList<>();
        for(int i = 0; i < graph.length; i++)
            nodes.add(i);
        ufs.makeSets(nodes);
        for(int i = 0; i < graph.length; i++){
            int cur = i;
            int[] neighbors = graph[cur];
            for(int neighbor : neighbors){
                if(ufs.findHead(neighbor) == ufs.findHead(cur))
                    return false;
                ufs.union(neighbor, neighbors[0]);
            }
        }
        return true;
    }

    public static class UnionFindSet {
        public HashMap<Integer, Integer> fatherMap;   //key为child，value为father
        public HashMap<Integer, Integer> sizeMap;	//value为key所在的集合的大小是多少

        public UnionFindSet() {
            fatherMap = new HashMap<Integer, Integer>();
            sizeMap = new HashMap<Integer, Integer>();
        }

        public void makeSets(List<Integer> nodes) {
            for (int node : nodes) {
                fatherMap.put(node, node);   //在最开始，每一个节点自己成一个集合
                sizeMap.put(node, 1);
            }
        }
        //给一个元素node，返回它所处集合的代表节点。在这个过程中将链变扁平
        private int findHead(int node) {
            int father = fatherMap.get(node);
            if (father != node) {
                father = findHead(father);
            }
            fatherMap.put(node, father);
            return father;
        }

        public void union(int a, int b) {
            int aHead = findHead(a);
            int bHead = findHead(b);
            if (aHead != bHead) {
                int aSetSize= sizeMap.get(aHead);
                int bSetSize = sizeMap.get(bHead);
                if (aSetSize <= bSetSize) {
                    fatherMap.put(aHead, bHead);
                    sizeMap.put(bHead, aSetSize + bSetSize);
                } else {
                    fatherMap.put(bHead, aHead);
                    sizeMap.put(aHead, aSetSize + bSetSize);
                }
            }
        }
    }
}

参考