無向グラフでDFSを使用して接続されたすべてのコンポーネントを検索する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("The connected components are :")
print(conn_comp)

出力

1-->0
2-->3
3-->0
The connected components are :
[[0, 1, 3, 2], [4]]

説明

• 「Graph_struct」という名前のクラスが定義されています。

• ツリーに要素を追加するのに役立つ「add_edge」という名前のメソッドが定義されています。

• 深さ優先探索アプローチを使用してツリーをトラバースするのに役立つ「DFS_Utility」メソッドが定義されています。

• 「connected_components」という名前のメソッドが定義されています。これは、相互に接続されているノードを判別するのに役立ちます。

• クラスのインスタンスが作成され、そのインスタンスでメソッドが呼び出されます。

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

• 接続されたコンポーネントは、コンソールに出力として表示されます。