Pythonで無向グラフのすべての連結成分をDFSで検索する方法

無向グラフに含まれるすべての連結成分（Connected Components）を検索するには、グラフを扱うクラスを作成し、頂点の初期化、辺の追加、深さ優先探索（DFS）による連結成分の検出といったメソッドを定義します。クラスのインスタンスを生成することで、これらのメソッドにアクセスして自由に利用できます。

以下に具体的な実装例を示します。

サンプルコード

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__」メソッドで頂点数と隣接リスト（adj）を初期化します。

• 「DFS_Utility」メソッドは、グラフの要素に対して深さ優先探索（DFS）を実行するためのものです。訪問済みの頂点を記録しながら、再帰的に探索を進めます。

• 「add_edge」メソッドは、グラフにノード間の辺を追加するためのものです。無向グラフであるため、両方向の接続情報を登録します。

• 「find_connected_components」メソッドは、各ノードに連結しているノード群（連結成分）を特定するためのものです。未訪問の頂点ごとにDFSを開始し、そこから到達できる頂点を1つの成分としてまとめていきます。

• 「Graph_structure」クラスのインスタンスを作成します。

• 「add_edge」メソッドを使って、グラフに辺を追加します。

• 追加された辺の情報をコンソールに表示します。

• 最後に「find_connected_components」を呼び出し、検出された連結成分の結果をコンソールに出力します。

この例では、6つの頂点を持つグラフに対して4本の辺を追加しています。実行結果を見ると、頂点 {0, 1, 5} と {2, 3, 4} の2つの連結成分が存在することが確認できます。このように、DFSを活用することで、無向グラフ全体を効率的に走査し、互いに接続されていない独立したグループを簡単に見つけ出すことができます。