用深度优先搜索在无向图中查找全部连通组件的Python程序

当需要使用深度优先搜索在无向图中查找所有连通组件时，定义了一个类，其中包含初始化值、执行深度优先搜索遍历、查找连通组件、添加节点到图形等方法。该类的实例可以被创建并访问方法，对其进行操作。

以下是同样操作的演示-

示例

class Graph_struct:
   def __init__(self, V):
      self.V = V
      self.adj = [[] for i in range(V)]

   def DFS_Utililty(self, temp, v, visited):

      visited[v] = True

      temp.append(v)

      for i in self.adj[v]:
         if visited[i] == False:
            temp = self.DFS_Utililty(temp, i, visited)
      return temp

   def add_edge(self, v, w):
      self.adj[v].append(w)
      self.adj[w].append(v)

   def connected_components(self):
      visited = []
      conn_compnent = []
      for i in range(self.V):
         visited.append(False)
      for v in range(self.V):
         if visited[v] == False:
            temp = []
            conn_compnent.append(self.DFS_Utililty(temp, v, visited))
      return conn_compnent

my_instance = Graph_struct(5)
my_instance.add_edge(1, 0)
my_instance.add_edge(2, 3)
my_instance.add_edge(3, 0)
print("1-->0")
print("2-->3")
print("3-->0")
conn_comp = my_instance.connected_components()
print("连通组件是：")
print(conn_comp)

输出

1 --> 0
2 --> 3
3 --> 0
连接的组件是：
[[0, 1, 3, 2], [4]]

说明

• 名称为“Graph_struct”的类已经定义。

• 已定义了一个名为“add_edge”的方法，它帮助将元素添加到树中。

• 定义了“DFS_Utility”方法，帮助使用深度优先搜索方法遍历树。

• 定义了一个名为“connected_components”的方法，它可帮助确定彼此连接的节点。

• 已创建类的实例，并在其上调用了方法。

• 节点将显示在控制台上。

• 结果连接的组件将显示在控制台上。