【算法】二分图判定

ゝ一纸荒年。 2023-10-07 22:42 47阅读 0赞

#### 目录 ####

*  1.概述
 *  2.代码实现
 *  3.应用

> 本文参考：  
> [LABULADONG 的算法网站][LABULADONG]

## 1.概述 ##

（1）**二分图 (Bipartite Graph)**，又称为**二部图**，是图论中的一种特殊模型。 设 G = (V, E) 是一个**无向图**，如果顶点 V 可分割为两个互不相交的子集 A 和 B，并且图中的每条边 (i, j) 所关联的两个顶点 i 和 j 分别属于这两个不同的顶点集，则称图 G 为一个二分图。

（2）二分图的判定其实就等同于图的**双色问题**，双色问题即：**给你一幅图，请你用两种颜色将图中的所有顶点着色，且使得任意一条边的两个端点的颜色都不相同，你能做到吗？**

（3）例如，下图就是一个二分图。  
![在这里插入图片描述][2373b3f2de1f42baafa7bceaf7128134.png]

## 2.代码实现 ##

（1）使用 BFS 来判定二分图的代码实现如下：

class Solution {
        
        // flag 用于标记该图是否为二分图
        boolean flag = true;
        // color 记录图中节点的颜色，false 和 true 分别代表两种不同的颜色
        boolean[] color;
        // visited 记录图中的节点是否被访问过
        boolean[] visited;
        
        // adjMatrix 为邻接矩阵
        public boolean isBipartite(int[][] adjMatrix) {
        
            //n 为节点个数
            int n = adjMatrix.length;
            //初始化
            color = new boolean[n];
            visited = new boolean[n];
            /*
                因为图不一定是联通的，可能存在多个子图，所以要把每个节点都作为起点进行一次遍历
                如果发现任何一个子图不是二分图，整幅图都不算二分图
            */
            for (int v = 0; v < n; v++) {
        
                if (!visited[v]) {
        
                    bfs(adjMatrix, v);
                }
            }
            return flag;
        }
        
        // BFS
        public void bfs(int[][] adjMatrix, 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 : adjMatrix[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;
                        }
                    }
                }
            }
        }
    }

（2）使用 DFS 来判定二分图的代码实现如下：

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

> 有关 BFS 的具体细节可以参考[【算法】广度优先遍历 (BFS)][_BFS] 这篇文章。  
> 有关 DFS 的具体细节可以参考[【算法】深度优先遍历 (DFS)][_DFS] 这篇文章。

## 3.应用 ##

（1）LeetCode 中的[886.可能的二分法][886.]这题便是对二分图判定的应用：

![在这里插入图片描述][9d6e5855ecd84a2c8ceab424d8f3af69.png]

该题的本质就是二分图的判定，只不过本题需要先通过数组 dislikes 来构建图，代码实现如下：

class Solution {
        
        //flag 用于标记该图是否为二分图
        boolean flag = true;
        //color 记录图中节点的颜色，false 和 true 分别代表两种不同的颜色
        boolean[] color;
        //visited 记录图中的节点是否被访问过
        boolean[] visited;
    
        public boolean possibleBipartition(int n, int[][] dislikes) {
        
            //初始化，节点编号从 1 开始
            color = new boolean[n + 1];
            visited = new boolean[n + 1];
            //构建图
            List<Integer>[] graph = buildGraph(n, dislikes);
            for (int v = 1; v <= n; v++) {
        
                if (!visited[v]) {
        
                    DFS(v, graph);
                }
            }
            return flag;
        }
    
        /*
            利用题目所给信息构建无向图，通过邻接表存储
            其中 n 表示节点个数，dislikes 存储节点之间的关系 
        */
        public List<Integer>[] buildGraph(int n, int[][] dislikes) {
        
            //图节点编号为 1...n
            List<Integer>[] graph = new LinkedList[n + 1];
            //创建 n 个节点
            for (int i = 1; i <= n; i++) {
        
                graph[i] = new LinkedList<>();
            }
            //创建节点之间的关系(即无向边)
            for (int[] edge : dislikes) {
        
                int v = edge[1];
                int w = edge[0];
                //无向图相当于双向图
                // v -> w
                graph[v].add(w);
                // w -> v
                graph[w].add(v);
            }
            return graph;
        }
    
        public void DFS(int v, List<Integer>[] graph) {
        
            if (flag == false) {
        
                return;
            }
            visited[v] = true;
            for (int w : graph[v]) {
        
                if (visited[w] == false) {
        
                    //节点 w 未被访问过
                    color[w] = !color[v];
                    DFS(w, graph);
                } else {
        
                    //节点 w 已被访问过
                    if (color[w] == color[v]) {
        
                        flag = false;
                        return;
                    }
                }
            }
        }
    }

（2）大家可以去 LeetCode 上找相关的二分图判定的题目来练习，或者也可以直接查看[LeetCode算法刷题目录（Java）][LeetCode_Java]这篇文章中的二分图章节。如果大家发现文章中的错误之处，可在评论区中指出。

[LABULADONG]: https://labuladong.gitee.io/algo/
[2373b3f2de1f42baafa7bceaf7128134.png]: https://img-blog.csdnimg.cn/2373b3f2de1f42baafa7bceaf7128134.png
[_BFS]: https://blog.csdn.net/weixin_43004044/article/details/128649433
[_DFS]: https://blog.csdn.net/weixin_43004044/article/details/128654426
[886.]: https://leetcode-cn.com/problems/possible-bipartition
[9d6e5855ecd84a2c8ceab424d8f3af69.png]: https://img-blog.csdnimg.cn/9d6e5855ecd84a2c8ceab424d8f3af69.png
[LeetCode_Java]: https://blog.csdn.net/weixin_43004044/article/details/122477673