当前位置： 移动技术网 > IT编程>脚本编程>Python > Leetcode算法题二分图Python3解法（88%时间 100%空间）

Leetcode算法题二分图Python3解法（88%时间 100%空间）

2020年07月18日  | 移动技术网IT编程  | 我要评论

先放题目：
给定一个无向图graph，当这个图为二分图时返回true。
如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。
graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。

示例 1:
输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释:
无向图如下:
0----1
| |
| |
3----2
我们可以将节点分成两组: {0, 2} 和 {1, 3}，所以返回为true

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

题目解析：
这个题目还算是比较绕的，其实就是要判断无向图是否能将所有边的端点各自划分到两个没有交集的集合中去。最简单直接的方法就是染色法+广度优先遍历。将起始的节点定义为红色，随后进行广度优先遍历，将A的邻居节点定义为蓝色，随后以这些邻居节点为起点再次遍历，在将它们的邻居节点定义为红色。那么如果在遍历的过程中，我们观察到存在这么一个节点，它的颜色与它邻居的颜色相同，那么我们就可以说这是一个“非二分图”
值得注意的点是，测试用例给出的无向图有可能不是联通图，所以要遍历所有的节点，否则有可能出错。
代码如下：


```python
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        color = [0 for i in range(len(graph))] 
        #初始化颜色数组，红色为1，蓝色为-1
        for i in range(len(graph)): #遍历graph中的全部节点
            if color[i] == 0: 
            #当一个节点仍为无色结点的时候，将其染成红色，并且入队
                color[i] = 1
                q = [i] #用一个list实现队列
                while q:
                    cur = q.pop(0) #弹出队首元素，并且获得他的邻居节点
                    for n in graph[cur]:
                        if color[n] == 0: 
                        #邻居节点无色的时候，将其设置为蓝色，并且加入队列
                            color[n] = -color[cur]
                            q.append(n)
                        elif color[n] == color[cur]:
                        #邻居节点与当前节点颜色相同，返回False
                            return False
        #全部遍历完没有返回False，就直接返回True
        return True

附上结果图片
在这里插入图片描述

本文地址：https://blog.csdn.net/qq_43324702/article/details/107377016

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网