Python中的二分图

2025 年 1 月 5 日 | 11 分钟阅读

在本教程中，我们将学习二分图以及检查给定图是否为二分图的方法。

二分图是指可以将其顶点分成两个独立集合的图。设这两个集合为 S1 和 S2。这两个集合将包含元素 s1 和 s2，其中 s1 和 s2 通过图中的边相连。因此，元素 (s1, s2) 是将顶点从集合 S1 连接到第二个集合的顶点 s2 的边。此外，一个集合中的元素不能相互连接。

如果可以使用两种颜色为图的顶点着色，并且所有相邻节点的对都具有不同的颜色，则称该图为二分图。

如果可以使用两种颜色进行图着色，使得集合中的顶点着相同的颜色，则二分图是可能的。请注意，具有偶数环的循环图可以使用两种颜色进行着色。例如，请参见下图。

具有奇数环的循环图无法使用两种颜色进行着色。

检查图是否为二分图的算法

检查图是否为二分图的简单方法是为每个节点着色。我们将使用两种颜色，并为每个节点着上替代颜色。如果我们能够为每个节点着色，并且没有相邻节点具有相同的颜色，那么该图就是二分图；否则，它就不是。

我们将为当前顶点着色，并为其邻居着上替代颜色。这样，我们将遍历每个顶点并为节点着色。如果在任何时候发现父节点和相邻节点具有相同的颜色，我们将停止算法并打印出给定图不是二分图。

代码

# Python program to find if the given graph is Bipartite or not using the BFS algorithm

# Defining a constructor class for the graph
class Graph():

  # Defining the method that will initialize the adjacency matrix of the graph
  def __init__(self, vertex):
    self.V = vertex
    self.matrix = [[0 for i in range(vertex)] for j in range(vertex)]

  # Defing a function that will use BFS traversal to traverse the given graph and will return True if the given graph is bipartite
  def checkBipartite(self, src):

    # We will create an array that will store the color of all the nodes of the graph.
    # Each index represents the ith vertex. Hence, we can access a vertex using indexing
    # Initially, each vertex will have the color -1.
    # We will give the source node color 0 to initiate the process.
    # During traversal, the rest of the colors will be updated. If two adjacent vertices have the same color, we will return False
    a = [-1] * self.V

    # Assigning the source node as color 0
    a[src] = 0

    # Initializing a queue and adding the source node to it
    q = []
    q.append(src)

    # Now, we will start the BFS traversal. The traversal will go on until the queue has elements
    while q:

      n = q.pop()

      # If the current node points to itself, we will return False
      if self.matrix[n][n] == 1:
        return False;

      # Traversing the elements that are adjacent to the current node
      for v in range(self.V):

        # If there is an edge between n and v and the color of v is not marked before, it is -1.
        if self.matrix[n][v] == 1 and a[v] == -1:

          # We will assign an alternate color of v to n
          a[v] = 1 - a[n]
          q.append(v)

        # Now, we will check if the end nodes of the current edge have the same colors. If yes, then we will return False
        elif self.matrix[n][v] == 1 and a[v] == a[n]:
          return False

    # If the traversal is completed without returning False, that means the graph is bipartite; hence, we will return True
    return True

# Creating a graph and passing it to the function
g = Graph(5)
g.matrix = [[0, 1, 1, 1, 0],
      [1, 0, 1, 1, 0],
      [1, 1, 0, 1, 1],
      [1, 1, 1, 0, 0],
      [0, 0, 1, 0, 0]
      ]

# Checking if the given graph is bipartite
if g.checkBipartite(0):
  print("The graph is a Bipartite graph")
else: print("The given graph is not a Bipartite graph")

输出

The given graph is not a Bipartite graph

时间复杂度：我们正在遍历大小为 V * V 的邻接矩阵的元素。在最坏的情况下，我们将遍历矩阵的每个元素；因此，时间复杂度为 O(V * V)。

空间复杂度：我们创建了一个队列和一个数组来存储顶点的颜色。因此，空间复杂度为 O(V)。

我们创建的算法仅适用于单连通图。如果图有多个组件，则只会遍历一个组件。我们需要修改代码，使其适用于多个组件。我们将从源 0 开始，并且我们知道连通的节点将被访问。没有边的图是二分图。这是因为，在二分图中，单个集合中的节点不应与其自身相连。

我们将修改代码以处理这些情况。将为图的每个组件调用 BFS 遍历，直到访问完图的所有节点。

代码

# Python program to tell if the given connected graph is bipartite or not

# Defining a constructor class for the graph
class Graph():

  # Defining the method that will initialize the adjacency matrix of the graph
  def __init__(self, vertex):
    self.V = vertex
    self.matrix = [[0 for i in range(vertex)] for j in range(vertex)]


  # Defining a function that will perform the BFS traversal on the nodes connected to the given source node
  # We will call this function for all the components of the graph
  def checkBipartite(self, src):

    # We will create an array that will store the color of all the nodes of the graph.
    # Each index represents the ith vertex. Hence, we can access a vertex using indexing
    # Initially, each vertex will have the color -1.
    # We will give the source node color 0 to initiate the process.
    # During traversal, the rest of the colors will be updated. If two adjacent vertices have the same color, we will return a False

    # Assigning the source node as color 0
    self.color[src] = 0

    # Initializing a queue and adding the source node to it
    q = []
    q.append(src)

    # Now, we will start the BFS traversal. The traversal will go on until the queue has elements
    while q:

      n = q.pop()

      # If the current node points to itself, we will return False
      if self.matrix[n][n] == 1:
        return False;

      # Traversing the elements that are adjacent to the current node
      for v in range(self.V):

        # If there is an edge between n and v and the color of v is not marked before, it is -1.
        if self.matrix[n][v] == 1 and self.color[v] == -1:

          # We will assign an alternate color of v to n
          self.color[v] = 1 - self.color[n]
          q.append(v)

        # Now, we will check if the end nodes of the current edge have the same colors. If yes, then we will return False
        elif self.matrix[n][v] == 1 and self.color[v] == self.color[n]:
          return False

    # If the traversal is completed without returning False, that means the graph is bipartite; hence, we will return True
    return True

  # This function will check if the complete graph is bipartite or not. For a complete graph to be bipartite, each component of the graph should be bipartite individually.
  def isBipartite(self):

    # Initializing the matrix that will store the color of the nodes
    self.color = [-1 for i in range(self.V)]
    for i in range(self.V):
      # If the node is not yet colored, we will call the BFS traversal function for this node to color to this node and all the adjacent nodes
      if self.color[i] == -1:
        if not self.checkBipartite(i):
          return False
    return True

# Creating a graph and passing it to the function
g = Graph(5)
g.matrix = [[0, 1, 1, 1, 0],
      [1, 0, 1, 1, 0],
      [1, 1, 0, 1, 1],
      [1, 1, 1, 0, 0],
      [0, 0, 1, 0, 0]
      ]

# Checking if the given graph is bipartite
if g.isBipartite():
  print("The graph is a Bipartite graph")
else: print("The given graph is not a Bipartite graph")

输出

The given graph is not a Bipartite graph

时间复杂度：我们遍历总的顶点和边数。因此，时间复杂度为 O(V + E)。

空间复杂度：我们创建了一个数组来存储已访问的节点。因此，空间复杂度为 O(V)。

在上面的示例中，图由邻接矩阵表示。如果图由邻接列表表示怎么办？因此，现在我们将看到邻接列表上的 BFS 遍历。此算法的时间复杂度将为 O(V + E)。这是一个通用算法，适用于单连通图和多连通图。

代码

# Python program to tell if the given graph in the form of an adjacency list is bipartite or not

# Defining a constructor class for the graph
class Graph:

  # Constructor to construct a graph with the given number of vertices
  def __init__(self, v):

    # Initializing the given number of vertices
    self.V = v

    # Creating a List to store the nodes of the graph
    self.adj_list = [[] for i in range(self.V)]

  # Defining the function to add an edge to the graph
  def Edge(self, u, v):
    # Since it is an undirected graph, u and v will be added to the neighborhood list of each other
    # Adding the vertex v to the neighbors' list of u
    self.adj_list[v].append(u)

    # Adding the vertex u to the neighbors' list of v
    self.adj_list[u].append(v)


  # Defing a function that will use BFS traversal to traverse the given graph and will return True if the given graph is bipartite
  def isBipartite(self):

    # Creating a vector to store the colors of the nodes. We will initialize the vector by giving the color -1 to each node
    # later, the nodes will be marked 0 and 1 alternatively.
    # If any two adjacent nodes have the same color values, the graph is not bipartite
    col = [-1] * self.V
   
    # Creating a queue to perform the BFS traversal.
    # This queue will store the node and the color of this node
    q = []
   
    # Creating a loop to traverse all the nodes to keep in check the connected components of the graph
    for src in range(self.V):
     
      # If the current node is not colored or not visited
      if (col[src] == -1):
       
        # putting the current source node in the queue and giving it the color 0
        q.append([src, 0])

        # Also marking the color in the col array
        col[src] = 0
       
       # Running a while loop until the queue is not empty
        while len(q) != 0:

          # Getting the current node n and its color c from the queue
          n, c = q.pop()
           
          # Running a for loop to traverse the nodes connected to the current node and adding those nodes to the queue
          for a in self.adj_list[n]:
           
            # If the current node is already colored, we will check if its color is the same as the color of the parent node
            if (col[a] == c):
              # if yes, then the graph is not bipartite
              return False
           
            # If the current node is not colored
            if (col[a] == -1):
             
              # We will give the current node the opposite color than the color of the parent node
              if c == 1:
                col[a] = 0
              else:
                col[a] = 1
              # Adding the node to the queue
              q.append([a, col[a]])
    
    # If all vertices of the graph are colored alternatively with 0 and 1, then the graph is bipartite. Hence, return True
    return True

# Creating a graph
g = Graph(9)
g.Edge(1, 2)
g.Edge(1, 5)
g.Edge(2, 3)
g.Edge(2, 1)
g.Edge(3, 2)
g.Edge(3, 4)
g.Edge(4, 3)
g.Edge(4, 8)
g.Edge(5, 1)
g.Edge(5, 6)
g.Edge(6, 7)
g.Edge(6, 5)
g.Edge(7, 6)
g.Edge(7, 8)
g.Edge(8, 7)
g.Edge(8, 2)

check = g.isBipartite()

if (check):
  print("The graph is a bipartite graph")
else:
  print("The graph is not a bipartite graph")

输出

The graph is a bipartite graph

时间复杂度：此方法的时间复杂度与上一个算法相同，即 O(V * V)。

空间复杂度：我们创建了一个数组来存储已访问的节点。因此，空间复杂度为 O(V)。

让我们看看如果给定图的邻接列表，如何检查图是否为二分图

代码

# Python program to tell if the given connected graph is bipartite or not

# Defining a constructor class for the graph
class Graph():

  # Defining the method that will initialize the adjacency matrix of the graph
  def __init__(self, vertex):
    self.V = vertex
    self.matrix = [[0 for i in range(vertex)] for j in range(vertex)]

  # Defining a function that will perform the BFS traversal on the nodes connected to the given source node
  # We will call this function for all the components of the graph
  def checkBipartite(self, src):

    # We will create an array that will store the color of all the nodes of the graph.
    # Each index represents the ith vertex. Hence, we can access a vertex using indexing
    # Initially, each vertex will have the color -1.
    # We will give the source node color 0 to initiate the process.
    # During traversal, the rest of the colors will be updated. If two adjacent vertices have the same color, we will return a False

    # Assigning the source node as color 0
    self.color[src] = 0

    # Initializing a queue and adding the source node to it
    q = []
    q.append(src)

    # Now, we will start the BFS traversal. The traversal will go on until the queue has elements
    while q:

      n = q.pop()

      # If the current node points to itself, we will return False
      if self.matrix[n][n] == 1:
        return False;

      # Traversing the elements that are adjacent to the current node
      for v in range(self.V):

        # If there is an edge between n and v and the color of v is not marked before hence is -1.
        if self.matrix[n][v] == 1 and self.color[v] == -1:

          # We will assign an alternate color of v to n
          self.color[v] = 1 - self.color[n]
          q.append(v)

        # Now, we will check if the end nodes of the current edge have the same colors. If yes, then we will return False
        elif self.matrix[n][v] == 1 and self.color[v] == self.color[n]:
          return False

    # If the traversal is completed without returning False, that means the graph is bipartite; hence, we will return True
    return True

输出

The graph is a bipartite graph

时间复杂度：如果以邻接列表的形式遍历图，时间复杂度将降低到 O(V + E)，其中 V 是图中的顶点数，E 是图中的边数。

空间复杂度：我们创建了一个数组来存储已访问的节点。因此，空间复杂度为 O(V)。

下一主题检测无向图中的环（Python）

Python中的二分图

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

其他

Python中的二分图

相关帖子

Python中的传教士和食人族问题

Python中的嵌套函数是如何工作的

最好的Python数据结构和算法课程

Python程序：从字符串形式的数字中删除前导零

如何在Python中按空格拆分字符串

Python中的数据操作

Python的Smartsheet API

Python中的Pandas Series.str.extract()

如何在Python中将Date转换为Datetime

Python图算法

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器