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

当需要查找树的所有节点的总和时，将创建一个类，该类包含设置根节点，向树中添加元素，搜索特定元素以及将树中的元素添加至的方法。找到总和，依此类推。可以创建该类的实例来访问和使用这些方法。

以下是相同的演示-

示例

class Graph_structure:

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

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

      visited[v] = True

      temp.append(v)

      for i in self.adj[v]:
         if visited[i] == False:

            temp = self.DFS_Utility(temp, i, visited)
      return temp

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

   def find_connected_components(self):
      visited = []
      connected_comp = []
      for i in range(self.V):
         visited.append(False)
      for v in range(self.V):
         if visited[v] == False:
            temp = []
            connected_comp.append(self.DFS_Utility(temp, v, visited))
      return connected_comp

my_instance = Graph_structure(6)
my_instance.add_edge(1, 0)
my_instance.add_edge(2, 3)
my_instance.add_edge(3, 4)
my_instance.add_edge(5, 0)
print("There are 6 edges. They are : ")
print("1-->0")
print("2-->3")
print("3-->4")
print("5-->0")

connected_comp = my_instance.find_connected_components()
print("连接的组件是...")
print(connected_comp)

There are 6 edges. They are :
1-->0
2-->3
3-->4
5-->0
连接的组件是...
[[0, 1, 5], [2, 3, 4]]

解释

• 使用“ _init_”方法定义了一个名为“ Graph_structure”的类。

• 定义了一种名为“ DFS_Utility”的方法，该方法有助于对图形的元素执行深度优先遍历。

• 定义了另一个名为“ add_edge”的方法，该方法有助于将节点添加到图中。

• 定义了另一种名为“ find_connected_components”的方法，该方法有助于确定连接到特定节点的节点。

• 创建了“ Graph_structure”的实例。

• 使用'add_edge'方法向其中添加元素。

• 它显示在控制台上。

• 将调用“ find_connected_components”，并在控制台上显示输出。