0%

leetcode每日一题-判断二分图

Posted on Edited on In ,

判断二分图

image1

image2

可以使用染色法解决，首先选定一个节点进行染色比如红色，与之连接的节点就染成绿色，之后再遍历这些染成绿色节点的连接节点，将它们染成红色，在染色的过程中如果发现节点已经染了色但是与即将染的颜色不同，说明不是二分图，否则就是二分图。算法流程如下：

  • 我们任选一个节点开始，将其染成红色，并从该节点开始对整个无向图进行遍历；
  • 在遍历的过程中，如果我们通过节点 $u$遍历到了节点$v$ （即 $u$和$v$在图中有一条边直接相连），那么会有两种情况：
    1. 如$v$未被染色，那么我们将其染成与 $u$ 不同的颜色，并对 $v$ 直接相连的节点进行遍历；
    2. 如果 $v$ 被染色，并且颜色与 $u$ 相同，那么说明给定的无向图不是二分图。我们可以直接退出遍历并返回 $False$ 作为答案。
  • 当遍历结束时，说明给定的无向图是二分图，返回 $True$作为答案。

可以使用深度优先搜索或者广度优先搜索。

注意：题目中给定的无向图不一定保证连通，因此我们需要进行多次遍历，直到每一个节点都被染色，或确定答案为 $False$ 为止。每次遍历开始时，我们任选一个未被染色的节点，将所有与该节点直接或间接相连的节点进行染色。

广度优先搜索：

1
class Solution {
2
    public static final int UNCOLORED = 0;
3
    public static final int RED = 1;
4
    public static final int GREEN = 2;
5
    public int[] color;
6
    public boolean isBipartite(int[][] graph) {
7
        int n = graph.length;
8
        color = new int[n];
9
        Arrays.fill(color, UNCOLORED);
10
        for(int i=0; i<n; i++){
11
            if(color[i] == UNCOLORED){
12
                Queue<Integer> queue = new LinkedList<Integer>();
13
                color[i] = RED;
14
                queue.offer(i);
15
                while(!queue.isEmpty()){
16
                    int node = queue.poll();
17
                    int nextcolor = color[node]==RED ? GREEN:RED;
18
                    for(int j : graph[node]){
19
                        if(color[j] == UNCOLORED){
20
                            color[j] = nextcolor;
21
                            queue.offer(j);
22
                        }else if(color[j] != nextcolor){
23
                            return false;
24
                        }
25
                    }
26
                }
27
            }
28
        }
29
        return true;
30
31
    }
32
}

深度优先搜索：

1
class Solution {
2
    public static final int UNCOLORED = 0;
3
    public static final int RED = 1;
4
    public static final int GREEN = 2;
5
    public int[] color;
6
    public boolean valid;
7
    public boolean isBipartite(int[][] graph) {
8
        int n = graph.length;
9
        color = new int[n];
10
        Arrays.fill(color, UNCOLORED);
11
        valid = true;
12
        for(int i=0; i<n && valid; i++){
13
            if(color[i] == UNCOLORED){
14
                dfs(i, RED, graph);
15
            }
16
        }
17
        return valid;
18
    }
19
    public void dfs(int node, int c, int[][] graph){
20
        color[node] = c;
21
        int nextcolor = c==RED ? GREEN:RED;
22
        for(int i:graph[node]){
23
            if(color[i] == UNCOLORED){
24
                dfs(i, nextcolor, graph);
25
                if(!valid){
26
                    return;
27
                }
28
            }else if(color[i] != nextcolor){
29
                valid = false;
30
                return;
31
            }
32
        }
33
    }
34
}

复杂度分析：

  • 时间复杂度：$O(m+n)$，$m$和$n$分别是无向图中的边数和点数。
  • 空间复杂度：$O(n)$。