Python程序在无向图中使用DFS查找所有连接的组件

  • Z时代
  • 2024-01-10
  • 分类：综合

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

以下是相同的演示-

示例

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”的方法，该方法有助于确定彼此连接的节点。

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

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

  • 连接的组件在控制台上显示为输出。

以上是 Python程序在无向图中使用DFS查找所有连接的组件 的全部内容， 来源链接： utcz.com/z/343895.html

回到顶部