785. 判断二分图

浅浅的花香味﹌ 2024-03-27 08:44 96阅读 0赞

存在一个 无向图 ，图中有 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：**

![6428b356b9e4ed0d0384ef45f4143f75.jpeg][]

> 输入：graph = \[\[1,2,3\],\[0,2\],\[0,1,3\],\[0,2\]\]  
> 输出：false  
> 解释：不能将节点分割成两个独立的子集，以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。

**示例 2：**

![6f912db0c8a4681bd7e5b8eed3a35054.jpeg][]

> 输入：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

二分图的特点：

1，所有点将被分成独立的集合

2.每条边两端的点一定属于不同的集合

3.可能存在孤点

无向图特点：

图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

![77a3384b687342bdba078bc8cae95c9a.png][]

思路：

首先我们可以先从任意一个节点开始设置为绿色，然后将其相邻的所有节点染成绿色，以此类推，并不断进行遍历，直至所有节点均被染色，返回true；如果有节点已经存在了染色并与我们想让他染色的颜色不一致那么就返回false。

算法流程：

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

因此要进行遍历的话可以使用深度优先搜索算法和广度优先搜索

*  深度优先算法

从一个节点出发，每次都沿路径到不能再前进时才退回到最近的岔路口

这个图中到了4之后可以往1也可以往6，最后走完后又回到0，往旁边的节点走

![9fa8e1ac78b846fb9b01c2b03347db6e.png][]

*  广度优先算法

从0开始出发到1的时候不着急与1相邻连接的节点遍历，而是遍历与0相连的2，以此类推把与0相邻的节点都访问完之后再访问下一个节点的相邻节点，比如1的相邻节点4

![99b4607f39304f60a9c207ed5a3739b9.png][]

**方法一：深度优先搜索**

class Solution {
        private static final int UNCOLORED = 0;
        private static final int RED = 1;
        private static final int GREEN = 2;
        private int[] color;
        private boolean valid;
    
        public boolean isBipartite(int[][] graph) {
            int n = graph.length;
            valid = true;
            color = new int[n];
            Arrays.fill(color, UNCOLORED);
            for (int i = 0; i < n && valid; ++i) {
                if (color[i] == UNCOLORED) {
                    dfs(i, RED, graph);
                }
            }
            return valid;
        }
    
        public void dfs(int node, int c, int[][] graph) {
            color[node] = c;
            int cNei = c == RED ? GREEN : RED;
            for (int neighbor : graph[node]) {
                if (color[neighbor] == UNCOLORED) {
                    dfs(neighbor, cNei, graph);
                    if (!valid) {
                        return;
                    }
                } else if (color[neighbor] != cNei) {
                    valid = false;
                    return;
                }
            }
        }
    }

**方法二：广度优先搜索**

class Solution {
        private static final int UNCOLORED = 0;
        private static final int RED = 1;
        private static final int GREEN = 2;
        private int[] color;
    
        public boolean isBipartite(int[][] graph) {
            int n = graph.length;
            color = new int[n];
            Arrays.fill(color, UNCOLORED);
            for (int i = 0; i < n; ++i) {
                if (color[i] == UNCOLORED) {
                    Queue<Integer> queue = new LinkedList<Integer>();
                    queue.offer(i);
                    color[i] = RED;
                    while (!queue.isEmpty()) {
                        int node = queue.poll();
                        int cNei = color[node] == RED ? GREEN : RED;
                        for (int neighbor : graph[node]) {
                            if (color[neighbor] == UNCOLORED) {
                                queue.offer(neighbor);
                                color[neighbor] = cNei;
                            } else if (color[neighbor] != cNei) {
                                return false;
                            }
                        }
                    }
                }
            }
            return true;
        }
    }

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/is-graph-bipartite  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[6428b356b9e4ed0d0384ef45f4143f75.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/02037c3fb03c4fc290dbdcc6a9af118c.png
[6f912db0c8a4681bd7e5b8eed3a35054.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/d1bcc7f26d1949938474ffff5c76adea.png
[77a3384b687342bdba078bc8cae95c9a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/86cf22de02b841f188c8b2ad16ff220d.png
[9fa8e1ac78b846fb9b01c2b03347db6e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/1e813fd10a2544399f1fc045b5c368c8.png
[99b4607f39304f60a9c207ed5a3739b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/bd7a0c7531604dd4a4af7de73c915289.png