【Python】無向グラフの連結成分をDFS（深さ優先探索）で全て検索するプログラム

無向グラフにおいて、深さ優先探索（DFS）を使ってすべての連結成分（Connected Components）を求めたいケースは、グラフアルゴリズムの学習において非常に重要なトピックです。本記事では、クラスを定義し、その中に値の初期化、DFSによる探索、連結成分の検出、グラフへのノード追加などのメソッドを実装する方法を解説します。

クラスのインスタンスを作成すれば、これらのメソッドにアクセスして、さまざまな操作を実行できるようになります。

サンプルコード

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」メソッドは、深さ優先探索（DFS）のアプローチでグラフを再帰的に走査します。訪問済みのノードを記録しながら、到達可能なすべてのノードを一時リストに格納します。

• 「connected_components」メソッドは、互いに接続されているノードのグループ（連結成分）を特定します。まだ訪問していないノードが見つかるたびに、そこからDFSを開始して新しい連結成分を作成します。

• クラスのインスタンスを作成し、そのインスタンスに対して各メソッドを呼び出します。

• グラフのエッジ情報がコンソールに表示されます。

• 最後に、検出された連結成分が出力としてコンソールに表示されます。

実行結果の読み方

この例では5つのノードを持つグラフを作成しています。エッジ「1→0」「2→3」「3→0」を追加した結果、ノード {0, 1, 2, 3} は互いにつながっているため [[0, 1, 3, 2]] という1つの連結成分となり、どのエッジも持たないノード4は単独で [4] という別の連結成分として検出されます。