您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
golang中怎么利用leetcode 判断二分图，针对这个问题，这篇文章详细介绍了相对应的分析和解答，希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。
给定一个无向图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 []intfor i:=0;i<l;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 判断二分图问题的解答就分享到这里了，希望以上内容可以对大家有一定的帮助，如果你还有很多疑惑没有解开，可以关注亿速云行业资讯频道了解更多相关知识。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。