golang中怎么利用leetcode判断二分图

golang中怎么利用leetcode 判断二分图,针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。

创新互联建站主营张家界网站建设的网络公司,主营网站建设方案,成都App定制开发,张家界h5重庆小程序开发搭建,张家界网站营销推广欢迎张家界等地区企业咨询

给定一个无向图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}。

示例 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]里边。

解题思路

深度优先搜索着色

1,如果节点属于第一个集合,将其着为蓝色,否则着为红色。

2,只有在二分图的情况下,可以使用贪心思想给图着色:一个节点为蓝色,说明它的所有邻接点为红色,它的邻接点的所有邻接点为蓝色,依此类推。

3,使用数组(或者哈希表)记录每个节点的颜色: color[node]。颜色可以是 1,2,或者未着色(0)。

4,搜索节点时,需要考虑图是非连通的情况。

5,对每个未着色节点,从该节点开始深度优先搜索着色。每个邻接点都可以通过当前节点着相反的颜色。

6,如果存在当前点和邻接点颜色相同,则着色失败。

7,使用栈完成深度优先搜索,栈类似于节点的 “todo list”,存储着下一个要访问节点的顺序。在 graph[node] 中,对每个未着色邻接点,着色该节点并将其放入到栈中。

代码实现

func isBipartite(graph [][]int) bool {    l:=len(graph)
   if l<2{return true    }    color:=make([]int,l)    var q []int    for i:=0;i        if color[i]==0{           q=append(q,i)           for len(q)>0{               if color[q[0]]==0{                  color[q[0]]=1               }               for _,j:=range(graph[q[0]]){                   if  color[j]==0{                       q=append(q,j)                       if color[q[0]]==1{                           color[j]=2                       }else if color[q[0]]==2{                           color[j]=1                       }                   }else if color[q[0]]==color[j]{                       return false                   }               }               q=q[1:]           }        }    }        return true}

关于golang中怎么利用leetcode 判断二分图问题的解答就分享到这里了,希望以上内容可以对大家有一定的帮助,如果你还有很多疑惑没有解开,可以关注创新互联行业资讯频道了解更多相关知识。


网站名称:golang中怎么利用leetcode判断二分图
文章URL:http://scyanting.com/article/pesggo.html