Keshawn_lu's Blog

Leetcode 785. 判断二分图

图 广度优先搜索
字数统计: 940阅读时长: 3 min
2020/07/16 Share

题目简介：

给定一个无向图graph，当这个图为二分图时返回true。

如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。

graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。

1
2
3
4
5
6
7
8
9
10
示例 1:
输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释: 
无向图如下:
0----1
|    |
|    |
3----2
我们可以将节点分成两组: {0, 2} 和 {1, 3}。
1
2
3
4
5
6
7
8
9
10
示例 2:
输入: [[1,2,3], [0,2], [0,1,3], [0,2]]
输出: false
解释: 
无向图如下:
0----1
| \  |
|  \ |
3----2
我们不能将节点分割成两个独立的子集。

注意:

  • graph 的长度范围为 [1, 100]。
  • graph[i] 中的元素的范围为 [0, graph.length - 1]。
  • graph[i] 不会包含 i 或者有重复的值。
  • 图是无向的: 如果j 在 graph[i]里边, 那么 i 也会在 graph[j]里边。

思路：

首先对于图中的任意两个节点，若它们之间是有边相连的，那么它们必属于两个不同的集合。

如果给定的无向图连通，那么我们就可以任选一个节点开始，给它染成红色。随后我们对整个图进行遍历，将该节点直接相连的所有节点染成绿色，表示这些节点不能与起始节点属于同一个集合。我们再将这些绿色节点直接相连的所有节点染成红色，以此类推，直到无向图中的每个节点均被染色。

如果我们能够成功染色，那么红色和绿色的节点各属于一个集合，这个无向图就是一个二分图；如果我们未能成功染色，即在染色的过程中，某一时刻访问到了一个已经染色的节点，并且它的颜色与我们将要给它染上的颜色不相同，也就说明这个无向图不是一个二分图。

所以采用广度优先遍历的方法，定义一个队列，将遍历到的节点依次入队。

我们遍历所有节点，在遍历过程中，若通过节点u遍历到了节点v，即这两个节点是存在边的，此时存在三种情况：

  1. 节点v还未染色，给它染上与节点u不同的颜色，并入队。
  2. 节点v已染色，且和节点u颜色相同，说明该图不为二分图，返回false。
  3. 节点v已染色，但和节点u颜色不同，不用管，跳过即可。

当遍历结束时，说明给定的无向图是二分图，返回true。

tip:

  • 由于给定的图不一定是连通图，所以需要遍历所有节点。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {

        vector<int> color(graph.size(), 0); //未染色

        for(int i = 0; i < graph.size(); i++){

            if(graph[i].size() == 0)	//无顶点
                continue;

            if(color[i] == 0){	//未染色

                queue<int> q;
                color[i] = 1;
                q.push(i);

                while(!q.empty()){

                    int top = q.front();
                    int top_color = color[top];
                    q.pop();

                    for(int i = 0; i < graph[top].size(); i++){

                        //之前已被染色,且颜色相同
                        if(color[graph[top][i]] == top_color)   
                            return false;

                        else if(color[graph[top][i]] == 0){ //未被染色
                        
                            q.push(graph[top][i]);
                            //涂上不同颜色
                            color[graph[top][i]] = (top_color == 1) ? 2 : 1;
                        }
                    }
                }
            }
        }

        return true;

    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网