LeetCode 785. 判断二分图 | Python

根据上面的概念，第一个元素，也就是 graph[0] 为 [1, 3]，这里表示节点 0 相连的节点为 1, 3（如示例解释中的无向图），第二个元素 graph[1] 为 [0, 2]，表示节点 1 相连的节点为 0, 2，同样与上面图示的吻合，那么后面的节点就以这样的思路去理解。

现在题目要求，无向图是否为二分图？题目中给出二分图的概念：将图的节点集合分割为两个独立子集，图中每条边的两个节点分别来自两个集合，那么这个图就称为二分图。

根据前面的理解，我们可以通过遍历节点进行标记的方法去判断。从一个节点开始，先进行染色标记，对图进行遍历，当前节点的相连的所有节点都标记为与当前节点不同的颜色，表示这里两个相连的节点属于不同的集合，循环遍历。

上面的情况可能会出现以下的结果：

• 当所有节点都成功染色时，那么颜色会区分开，也就是不同颜色属于不同集合，那么返回 True，说明是二分图。
• 如果没有成功染色，也就是遍历的过程中，会出现节点已经被染色，并且节点颜色与此时要染色的颜色不同，说明出现冲突，直接返回 False，说明不是二分图。

上述染色过程如下：

具体的算法：

• 任一顶点开始遍历，遍历的过程中，对相邻的节点用不同的颜色进行标记；
• 如果相邻的顶点出现相同的颜色标记，则说明给定的无线图不是二分图；
• 如果所有的节点连通，且成功染色，则说明是二分图。

具体的代码实现如下（含深度优先搜索，广度优先搜索）。

# 深度优先搜索
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
 def dfs(graph, node, color, signed):
     # 先判断，该节点是否被标记染色，如果被染色，判断这个节点颜色与当前要标记的颜色是否相同
     if signed[node] != 0:
  return signed[node] == color

     # 对当前节点染色，然后对相邻的节点标记不同的颜色
     signed[node] = color
     for x in graph[node]:
  if not dfs(graph, x, -color, signed):
      return False
     return True

 length = len(graph)
 # 在这里，0：表示未标记，1、 -1：表示不同的两个颜色
 signed = [0] * length
 # 这里需要注意，有可能会存在顶点未被访问的情况，
 # 那么以这个顶点进行再一次访问
 for i in range(length):
     if (signed[i] == 0 and not dfs(graph, i, 1, signed)):
  return False

 return True



# 广度优先搜索
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
 from collections import deque
 # 创建队列
 queue = deque()

 length = len(graph)
 # 在这里，0：表示未标记，1、 -1：表示不同的两个颜色
 # 标记是否被染色
 signed = [0] * length
 # 可能出现节点未被标记，存在则从它开始进行下一轮的 bfs
 for i in range(length):
     if signed[i] != 0:
  continue

     queue.append(i)
     signed[i] = 1

     # 当一个节点出队后，要将相邻的节点进行标记不同颜色并入队
     while queue:
  node = queue.popleft()
  for x in graph[node]:
      # 如果当前节点的相邻节点已经被染色，且两者颜色相同，返回 False，表示无法成功染色
      if signed[x] == signed[node]:
   return False
      # 如果未标记，进行染色，与当前节点颜色不同，并入队
      if signed[x] == 0:
   signed[x] = -signed[node]
   queue.append(x)
 
 return True