無向グラフでBFSを使用してすべての連結成分を検索するPythonプログラム

ツリーのすべてのノードの合計を見つける必要がある場合は、クラスが作成されます。このクラスには、ルートノードの設定、ツリーへの要素の追加、特定の要素の検索、およびツリーの要素の追加を行うためのメソッドが含まれています。合計などを見つけます。これらのメソッドにアクセスして使用するために、クラスのインスタンスを作成できます。

以下は同じのデモンストレーションです-

例

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("The connected components are...")
print(connected_comp)

出力

There are 6 edges. They are :
1-->0
2-->3
3-->4
5-->0
The connected components are...
[[0, 1, 5], [2, 3, 4]]

説明

• 「Graph_structure」という名前のクラスが「_init_」メソッドで定義されています。

• グラフの要素で深さ優先探索を実行するのに役立つ「DFS_Utility」という名前のメソッドが定義されています。

• グラフにノードを追加するのに役立つ「add_edge」という名前の別のメソッドが定義されています。

• 「find_connected_components」という名前の別のメソッドが定義されており、特定のノードに接続されているノードを判別するのに役立ちます。

• 「Graph_structure」のインスタンスが作成されます。

• 「add_edge」メソッドを使用して要素が追加されます。

• コンソールに表示されます。

• 「find_connected_components」が呼び出され、出力がコンソールに表示されます。