算法-图染色法 DFS/BFS-判断二分图

刺骨的言语ヽ痛彻心扉 2023-02-27 05:39 64阅读 0赞

# 算法-图染色法 DFS/BFS-判断二分图 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/is-graph-bipartite/

## 1.2 题目描述 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]

# 2 图-DFS #

## 2.1 思路 ##

遍历所有节点进行染色，比如初始为白色，然后对直接相连的节点bfs染色为黑色。

然后对这些染为黑色的相邻节点也染色为白色，以此类推继续bfs染色。

如果要染色某节点时，要染的目标颜色和该节点的已经染过的颜色不同，则说明不能构成二分图。

## 2.2 代码 ##

class Solution { 
        // 0 表示未访问，1表示白色，2表示黑色
        int[] color;
        public boolean isBipartite(int[][] graph) { 
    
            // 任选一个节点进行染色为白色，然后对直接相连的节点bfs染色为黑色
            // 同时对这些染为黑色的相邻节点也染色为白色，以此类推继续bfs染色
            // 如果要染色某节点时，要染的目标颜色和该节点的已经染过的颜色不同，则说明不能构成二分图
           
            color = new int[graph.length];
    
            // 因为有可能是不连通的，所以需要遍历所有节点
            for(int i = 0; i < graph.length; i++){ 
                if(color[i] > 0){ 
                    // 已染色过的节点不再处理
                    continue;
                }
                // 第二次遍历到这里时，可以再次用1位目标颜色
                // 因为我们采用dfs，且过滤了已访问节点，连通图中的节点不会再次走这里
                if(dfs(graph, i, 1) == false){ 
                    return false;
                }
            }
            return true;
        }
    
        private boolean dfs (int[][] graph, int index, int targetColor){ 
            // 获取连接点
            int[] neighbour = graph[index];
            if(neighbour.length == 0){ 
                // 无邻接点的，不影响结果，返回true
                return true;
            }
    
            // 将当前节点染色
            color[index] = targetColor;
            // 改变邻接节点要染的目标颜色
            targetColor = targetColor == 1? 2 : 1; 
            
            // 遍历邻接节点，尝试将他们染为另外一种颜色
            for(int i = 0; i < neighbour.length; i++){ 
                if(color[neighbour[i]] == 0){ 
                    // 未访问过的节点，就进行dfs
                    if(dfs(graph, neighbour[i], targetColor) == false){ 
                        return false;
                    }
                }
                if(color[neighbour[i]] != targetColor){ 
                    // 如果要染色某节点时，要染的目标颜色和该节点的已经染过的颜色不同，
                    // 则说明不能构成二分图
                    return false;
                }
            }
            return true;
        }
    }

## 2.3 时间复杂度 ##

![在这里插入图片描述][20200716133940818.png]  
O(N+M)，其中N 和 M 分别是无向图中的点数和边数。

## 2.4 空间复杂度 ##

O(N)

*  递归栈深度最大为N。标记color的数组长度为N。

# 3 图-BFS #

## 3.1 思路 ##

遍历所有节点进行染色，比如初始为白色，然后对直接相连的节点bfs染色为黑色。

然后对这些染为黑色的相邻节点也染色为白色，以此类推继续bfs染色。

如果要染色某节点时，要染的目标颜色和该节点的已经染过的颜色不同，则说明不能构成二分图。

## 3.2 代码 ##

class Solution { 
        // 0 表示未访问，1表示白色，2表示黑色
        int[] color;
        public boolean isBipartite(int[][] graph) { 
    
            // 任选一个节点进行染色为白色，然后对直接相连的节点bfs染色为黑色
            // 同时对这些染为黑色的相邻节点也染色为白色，以此类推继续bfs染色
            // 如果要染色某节点时，要染的目标颜色和该节点的已经染过的颜色不同，则说明不能构成二分图
           
            color = new int[graph.length];
    
            // 因为有可能是不连通的，所以需要遍历所有节点
            for(int i = 0; i < graph.length; i++){ 
                if(color[i] > 0){ 
                    // 已染色过的节点不再处理
                    continue;
                }
                // 第二次遍历到这里时，可以再次用1位目标颜色
                // 因为我们采用bfs，且过滤了已访问节点，连通图中的节点不会再次走这里
                if(bfs(graph, i, 1) == false){ 
                    return false;
                }
            }
            return true;
        }
    
        private boolean bfs (int[][] graph, int index, int targetColor){ 
            Queue<int[]> queue = new LinkedList<>();
            int[] ele = { index, targetColor};
            queue.add(ele);
    
            while(queue.size() > 0){ 
                ele = queue.poll();
                index = ele[0];
                targetColor = ele[1];
                // 获取临接点
                int[] neighbour = graph[index];
                if(neighbour.length == 0){ 
                    // 无邻接点的，不影响结果，返回true
                    return true;
                }
    
                // 将当前节点染色
                color[index] = targetColor;
                // 改变邻接节点要染的目标颜色
                targetColor = targetColor == 1? 2 : 1;
    
                // 遍历邻接节点，进行bfs
                for(int i = 0; i < neighbour.length; i++){ 
                    if(color[neighbour[i]] == 0){ 
                        // 未访问过的节点，就进行dfs
                        queue.add(new int[]{ neighbour[i], targetColor});
                    } else if(color[neighbour[i]] != targetColor){ 
                        // 如果要染色某节点时，要染的目标颜色和该节点的已经染过的颜色不同，
                        // 则说明不能构成二分图
                        return false;
                    }
                } 
            }
            return true;
        }
    }

## 3.3 时间复杂度 ##

![在这里插入图片描述][20200716145612542.png]  
O(N+M)，其中N 和 M 分别是无向图中的点数和边数。

## 3.4 空间复杂度 ##

O(N)

*  标记color的数组长度为N。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]: /images/20230209/188d02772e07477ea57ff875a5df2f61.png
[20200716133940818.png]: /images/20230209/9e2a16ce096a4ab5b32259d0e97e62e0.png
[20200716145612542.png]: /images/20230209/8dc0bd43a3614402bc73bcd4eb27ec62.png