用 Python 编写程序检查给定图是否为二分图

pythonserver side programmingprogramming更新于 2026/1/8 20:28:17

假设我们有一个无向图，我们必须检查该图是否为二分图。我们知道，当我们可以将图的节点分成两个集合 A 和 B 时，图是二分图，这样图中的每个边 {u,v} 在 A 中都有一个节点 u，在 B 中有一个节点 v。

因此，如果输入如下

则输出将为 True，[0,4] 在集合 A 中，[1,2,3] 在集合 B 中，并且所有边都是从 A 到 B 或 B 到 A，而不是从 A 到 A 或 B 到 B。

为了解决这个问题，我们将遵循以下步骤−

定义一个函数 dfs() 。这将获取源
对于 graph[source] 中的每个顶点，执行
- 如果 color[vertex] 不等于 -1，则
  - 如果 color[vertex] 与 color[source] 相同，则
    - result[0] := False
    - 返回
  - 进行下一次迭代
- color[vertex] := 1 - color[source]
- dfs(vertex)
从主方法中，执行following−
n := arr 的大小
graph := 0 到 n-1 顶点的空邻接列表
对于 0 到 n 范围内的 i，执行
- 对于 arr[i] 中的每个 j，执行
  - 将 i 插入 graph[j]
  - 将 j 插入 graph[i]
- color := 大小为 n 的列表并用 -1 填充
- result := 具有一个 True 值的列表
对于 0 到 n 范围内的 i，执行
- 如果 color[i] 与 -1 相同，则
- dfs(i)
返回 result[0]

让我们看看下面的实现以便更好地理解 −

示例

from collections import defaultdict
class Solution:
   def solve(self, arr):
      n = len(arr)
      graph = [set() for i in range(n)]
      for i in range(n):
         for j in arr[i]:
            graph[j].add(i)
            graph[i].add(j)
      color = [-1] * n
      result = [True]
      def dfs(source):
      for child in graph[source]:
         if color[child] != -1:
            if color[child] == color[source]:
               result[0] = False
               return
            continue
      color[child] = 1 - color[source]
      dfs(child)
   for i in range(n):
      if color[i] == -1:
      dfs(i)
   return result[0]
ob = Solution()
graph = [[1,2,3],[0],[0,4],[0,4],[2,3]]
print(ob.solve(graph))