Pythonで有向グラフを反転するプログラムの書き方を解説

有向グラフが与えられたとき、その反転グラフ（逆グラフ）を求めることを考えてみましょう。反転とは、元のグラフにおいて u から v へ向かう辺 を、v から u へ向かう辺 に変える操作です。

入力は隣接リスト形式で与えられ、ノード数が n の場合、ノードは 0, 1, ..., n-1 という番号で表されます。

例えば、次のようなグラフが入力として与えられた場合：

出力は以下のようになります：

解法のアルゴリズム

この問題は、以下の手順で解くことができます。

• 頂点数 n と同じ長さの空リスト ans を用意します
• グラフの各インデックス i と、それに対応する隣接リスト l について処理を行います
  • l 内の各頂点 x に対して、ans[x] の末尾に i を追加します
• 最後に ans を返します

ポイントは、元のグラフに「i → x」という辺が存在するならば、反転グラフでは「x → i」という辺になるため、i を ans[x] に追加すればよい、という点です。これにより、すべての辺の向きを効率的に入れ替えることができます。

Pythonでの実装例

理解を深めるために、実際のコードを見てみましょう。

サンプルコード

class Solution:
    def solve(self, graph):
        ans = [[] for _ in graph]
        for i, l in enumerate(graph):
            for x in l:
                ans[x].append(i)
        return ans

ob = Solution()
graph = [[1,2],[4],[4],[1,2],[3]]
print(ob.solve(graph))

入力

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

出力

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

処理の流れを確認

上記の入力例では、頂点0から頂点1と2へ、頂点1から頂点4へ、頂点2から頂点4へ、頂点3から頂点1と2へ、そして頂点4から頂点3へと辺が伸びています。

反転後の出力を見ると：

• 頂点0へ入ってくる辺はないため [] （空リスト）
• 頂点1には頂点0と3からの辺があるため [0, 3]
• 頂点2にも頂点0と3からの辺があるため [0, 3]
• 頂点3には頂点4からの辺があるため [4]
• 頂点4には頂点1と2からの辺があるため [1, 2]

となり、すべての辺の向きが正しく反転されていることがわかります。

計算量

• 時間計算量： O(V + E) ― Vは頂点数、Eは辺数。すべての頂点と辺を一度ずつ走査するためです。
• 空間計算量： O(V + E) ― 反転グラフを格納するために新しい隣接リストが必要です。

このように、隣接リストを使えば有向グラフの反転は非常にシンプルに実装できます。グラフの転置は、強連結成分分解（SCC）などの高度なグラフアルゴリズムでも利用される重要な操作なので、ぜひマスターしておきましょう。