Pythonでグラフの頂点間の到達可能性行列を計算するプログラム

隣接リスト形式で表現されたグラフが与えられたとき、次のような条件を満たす2次元行列Mを求めることを考えます。

• M[i, j] = 1：頂点iから頂点jへの経路（パス）が存在する場合
• M[i, j] = 0：経路が存在しない場合

例えば、次のようなグラフが入力として与えられたとします。

この場合の出力は、以下の5×5の行列になります。

解法のアプローチ

この問題は、各頂点を起点とした幅優先探索（BFS）を用いることで効率的に解くことができます。具体的な手順は以下の通りです。

1. n×nの2次元行列「ans」を作成し、すべての要素を0で初期化します（nは頂点の総数）。
2. 起点となる頂点iを0からn-1まで順番に処理します。
   • キューqを作成し、最初にiを挿入します。
   • キューqが空になるまで、以下の処理を繰り返します。
     • キューの先頭要素をnodeとして取り出します。
     • すでにans[i][node]が1になっている場合は、重複処理を避けるため次の反復へスキップします。
     • ans[i][node]に1を設定します。
     • nodeの隣接ノード一覧（graph[node]）を取得し、それぞれをキューqの末尾に追加します。
3. すべての頂点について処理が完了したら、行列ansを返します。

それでは、実際の実装例を見てみましょう。

実装例

class Solution:
    def solve(self, graph):
        ans=[[0 for _ in graph] for _ in graph]
        for i in range(len(graph)):
            q=[i]
            while q:
                node=q.pop(0)
                if ans[i][node]: continue
                ans[i][node]=1
                neighbors=graph[node]
                for n in neighbors:
                    q.append(n)
        return ans
ob = Solution()
adj_list = [[1,2],[4],[4],[1,2],[3]]
print(ob.solve(adj_list))

入力

[[1,2],[4],[4],[1,2],[3]]

出力

[[1, 1, 1, 1, 1],
   [0, 1, 1, 1, 1],
   [0, 1, 1, 1, 1],
   [0, 1, 1, 1, 1],
   [0, 1, 1, 1, 1]
]

まとめ

このアルゴリズムでは、各頂点からBFSを実行することで、その頂点から到達可能なすべての頂点を効率的に特定できます。計算量はO(V×(V+E))となり、Vは頂点数、Eは辺の数です。なお、対角成分M[i, i]は常に1になる点にも注目してください。これは、各頂点から自分自身へは必ず到達できる（長さ0の経路が存在する）ためです。