785。判断二分图当此图是二分图时返回真。如果我们可以将一个图的节点集划分为两个独立的子集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我们不能将一个节点拆分成两个独立的子集。注意：图表的长度在[1,100]范围内。graph[i]中的元素具有范围[0,graph.length-1]。graph[i]将不包含i或具有重复值。图是无向的：如果j在graph[i]中，那么i也将在graph[j]中。解题思路：深度优先搜索，广度优先搜索先审题，这里，看题可能感觉有点乱。结合例子，【图会以邻接表的形式给出，graph[i]表示图中所有与节点i相连的节点】，见例1：输入：[[1,3],[0,2],[1,3],[0,2]]输出：true解释：无向图如下：0----1||||3----2根据上面的概念，第一个元素也是也就是graph[0]是[1,3]，也就是说与节点0相连的节点是1,3（比如无向图例子解释中的graph），第二个元素graph[1]为[0,2]，表示与节点1相连的节点为0和2，这也与上图一致，所以下面的节点可以是以这种方式理解。现在问题来了，无向图是二分图吗？题目中给出了二部图的概念：将图的节点集分成两个独立的子集，图中每条边的两个节点分别来自两个集合，那么这个图就称为二部图。按照前面的理解，我们可以通过遍历节点并标记来判断。从一个节点开始，先进行颜色标记，遍历图。所有与当前节点相连的节点都用与当前节点不同的颜色标记，表示这里相连的两个节点属于不同的集合，循环遍历。上述情况可能会出现以下结果：当所有节点都染色成功后，会区分颜色，即不同的颜色属于不同的集合，则返回True，说明是二分图。如果没有成功染色，即在遍历过程中，会出现该节点已经被染色，此时该节点的颜色与要染色的颜色不同，说明存在冲突，并直接返回False，说明不是二分图。上述着色过程如下：具体算法：任意一个顶点开始遍历，遍历过程中，用不同颜色标记相邻节点；如果相邻顶点出现相同的颜色标记，则表示给定的无线图不是二分图；如果所有节点都连接并成功着色，则它是一个二分图。具体代码实现如下（包括深度优先搜索，广度优先搜索）。代码实现#深度优先搜索类解决方案：defisBipartite(self,graph:List[List[int]])->bool:defdfs(graph,node,color,signed):#首先判断节点是否被标记和colored,如果是彩色,判断这个节点的颜色和当前要标记的颜色是否相同ifsigned[node]!=0:returnsigned[node]==color#给当前节点着色,然后标记具有不同颜色的相邻节点signed[node]=colorforxingraph[node]:ifnotdfs(graph,x,-color,signed):returnFalsereturnTruelength=len(graph)#这里，0:表示unmarked,1,-1:表示两种不同的颜色signed=[0]*length#这里需要注意的是，可能会出现该顶点还没有访问过的情况，#然后使用这个顶点再次访问foriinrange(length):if(signed[i]==0andnotdfs(graph,i,1,signed)):returnFalsereturnTrue#广度优先搜索类解决方案：defisBipartite(self,graph:List[List[int]])->布尔值：从集合导入deque#创建队列queue=deque()length=len(graph)#这里，0：表示未标记，1，-1：表示两种不同的颜色#标记是否着色signed=[0]*length#可能出现节点未标记，如果存在则开始下一轮fromitbfsforiinrange(length):ifsigned[i]!=0:continuequeue.append(i)signed[i]=1#当一个节点出队时，相邻节点要用不同的颜色标记Mergeintothequeuewhilequeue:node=queue.popleft()forxingraph[node]:#如果当前节点的相邻节点已经被染色，并且两者颜色相同，则返回False，表示不能染色successfulifsigned[x]==signed[node]:returnFalse#如果没有被标记，则会被着色，与当前节点的颜色不同，如果signed[x]==则会被入队0:signed[x]=-signed[node]queue.append(x)returnTrue实现结果深度优先搜索广度优先搜索欢迎关注公众号【图书收藏】
