LeetCode_二分图_中等_785. 判断二分图

左手的ㄟ右手 2023-10-06 22:37 57阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

存在一个无向图，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个**二维数组 graph**，其中 **graph\[u\] 是一个节点数组，由节点 u 的邻接节点组成**。形式上，对于 graph\[u\] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性：  
① 不存在自环（graph\[u\] 不包含 u）。  
② 不存在平行边（graph\[u\] 不包含重复值）。  
③ 如果 v 在 graph\[u\] 内，那么 u 也应该在 graph\[v\] 内（该图是无向图）  
④ 这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。  
**二分图定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为二分图 。**

如果图是二分图，返回 true ；否则，返回 false 。

**示例 1：**  
![在这里插入图片描述][7d44f4b975ba49b6a95452cc142dc681.png]  
输入：graph = \[\[1,2,3\],\[0,2\],\[0,1,3\],\[0,2\]\]  
输出：false  
解释：不能将节点分割成两个独立的子集，以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。

**示例 2：**  
![在这里插入图片描述][b168c817cfad4a8fa009e6484d4cedfa.png]  
输入：graph = \[\[1,3\],\[0,2\],\[1,3\],\[0,2\]\]  
输出：true  
解释：可以将节点分成两组: \{0, 2\} 和 \{1, 3\} 。

**提示：**  
graph.length == n  
1 <= n <= 100  
0 <= graph\[u\].length < n  
0 <= graph\[u\]\[i\] <= n - 1  
graph\[u\] 不会包含 u  
graph\[u\] 的所有值互不相同  
如果 graph\[u\] 包含 v，那么 graph\[v\] 也会包含 u

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/is-graph-bipartite

## 2.思路 ##

（1）二分图判定算法\_DFS  
其实二分图的判定就等同于**图的双色问题**，双色问题即：**给你一幅「图」，请你用两种颜色将图中的所有顶点着色，且使得任意一条边的两个端点的颜色都不相同，你能做到吗？** 思路参考[二分图判定][Link 1]。

（2）二分图判定算法\_BFS

## 3.代码实现（Java） ##

//思路1————二分图判定算法_DFS
    class Solution {
        
        //flag 用于标记该图是否为二分图
        boolean flag = true;
        //color 记录图中节点的颜色，false 和 true 分别代表两种不同的颜色
        boolean[] color;
        //visited 记录图中的节点是否被访问过
        boolean[] visited;
    
        public boolean isBipartite(int[][] graph) {
        
            //n 为节点个数
            int n = graph.length;
            //初始化
            color = new boolean[n];
            visited = new boolean[n];
            /*
                因为图不一定是联通的，可能存在多个子图，所以要把每个节点都作为起点进行一次遍历
                如果发现任何一个子图不是二分图，整幅图都不算二分图
            */
            for (int v = 0; v < n; v++) {
        
                if (visited[v] == false) {
        
                    DFS(graph, v);
                }
            }
            return flag;
        }
    
        //DFS
        public void DFS(int[][] graph, int v) {
        
            if (flag == false) {
        
                //如果已经确定该图不是二分图，则直接返回即可
                return;
            }
            //当前节点已经被访问
            visited[v] = true;
            //访问与 v 相邻的所有节点
            for (int w : graph[v]) {
        
                if (visited[w] == false) {
        
                    //相邻节点 w 没有被访问过，则应该给 w 涂上与 v 不同的颜色
                    color[w] = !color[v];
                    //继续遍历与 w 相邻的所有节点
                    DFS(graph, w);
                } else {
        
                    //相邻节点 w 没有被访问过，则应该判断 w 与 v 的颜色是否相同
                    if (color[w] == color[v]) {
        
                        //v 和 w 的颜色相同，则说明该图不是二分图，令 flag = false，然后直接返回即可
                        flag = false;
                        return;
                    }
                }
            }
        }
    }

//思路1————二分图判定算法_BFS
    class Solution {
        
        //flag 用于标记该图是否为二分图
        boolean flag = true;
        //color 记录图中节点的颜色，false 和 true 分别代表两种不同的颜色
        boolean[] color;
        //visited 记录图中的节点是否被访问过
        boolean[] visited;
    
        public boolean isBipartite(int[][] graph) {
        
            //n 为节点个数
            int n = graph.length;
            //初始化
            color = new boolean[n];
            visited = new boolean[n];
            /*
                因为图不一定是联通的，可能存在多个子图，所以要把每个节点都作为起点进行一次遍历
                如果发现任何一个子图不是二分图，整幅图都不算二分图
            */
            for (int v = 0; v < n; v++) {
        
                if (!visited[v]) {
        
                    BFS(graph, v);
                }
            }
            return flag;
        }
    
        //BFS
        public void BFS(int[][] graph, int start) {
        
            //定义队列
            Queue<Integer> queue = new LinkedList<>();
            //当前节点已经被访问
            visited[start] = true;
            //将当前节点存入队列中
            queue.offer(start);
            while (!queue.isEmpty() && flag) {
        
                //取出队首节点
                int v = queue.poll();
                //遍历与 v 相邻的所有节点
                for (int w : graph[v]) {
        
                    if (!visited[w]) {
        
                        //相邻节点 w 没有被访问过，则应该给 w 涂上与 v 不同的颜色
                        color[w] = !color[v];
                        //节点 w 已经被访问
                        visited[w] = true;
                        //将节点 w 存入队列
                        queue.offer(w);
                    } else {
        
                        //相邻节点 w 没有被访问过，则应该判断 w 与 v 的颜色是否相同
                        if (color[w] == color[v]) {
        
                            //v 和 w 的颜色相同，则说明该图不是二分图，令 flag = false，然后直接返回即可
                            flag = false;
                            return;
                        }
                    }
                }
            }
        }
    }

[7d44f4b975ba49b6a95452cc142dc681.png]: https://img-blog.csdnimg.cn/7d44f4b975ba49b6a95452cc142dc681.png
[b168c817cfad4a8fa009e6484d4cedfa.png]: https://img-blog.csdnimg.cn/b168c817cfad4a8fa009e6484d4cedfa.png
[Link 1]: https://labuladong.github.io/algo/2/20/50/