Pythonで与えられたグラフが2部グラフかどうかを判定するプログラム

2部グラフとは

無向グラフが与えられたとき、そのグラフが2部グラフ(バイパータイトグラフ)であるかどうかを判定する方法を解説します。

2部グラフとは、グラフのすべての頂点を2つの集合 A と B に分割でき、グラフ内のすべての辺 {u, v} が必ず一方の端点 u が集合 A、もう一方の端点 v が集合 B に属するようなグラフのことです。つまり、同じ集合内の頂点同士を結ぶ辺(A-A や B-B)が一切存在しないグラフです。

例として、次のようなグラフを考えてみましょう。

この場合、頂点 [0, 4] を集合 A に、[1, 2, 3] を集合 B に分類できます。すべての辺は A から B、または B から A に向かっており、A 内部や B 内部に辺が存在しないため、このグラフは2部グラフであり、出力は True となります。

アルゴリズムの考え方:2色塗り分け

2部グラフの判定にはDFS(深さ優先探索)による2色塗り分けが有効です。隣接する頂点同士を必ず異なる色で塗っていき、途中で「隣接頂点と同じ色になってしまった」箇所が見つかれば、そのグラフは2部グラフではありません。

手順

1. DFS用の関数 dfs() を定義します。引数は探索起点となる頂点 source です。
2. graph[source] に含まれる各頂点 vertex について次を処理します。
   • color[vertex] が -1 以外(=すでに塗られている)の場合:
     • color[vertex] が color[source] と同じなら、結果を False にして処理を終了します。
     • 色が異なる場合は何もせず次の頂点へ進みます。
   • まだ塗られていない場合は、color[vertex] = 1 - color[source] として反対の色を割り当て、そこから再帰的に DFS を実行します。
3. メイン処理では以下を行います。
   • n を入力配列のサイズとします。
   • 頂点 0 ~ n-1 の空の隣接リスト graph を作成します。
   • 各辺に対して、両方向の隣接関係をリストに登録します(無向グラフのため)。
   • サイズ n の色管理リスト color を作成し、すべて -1(未訪問)で初期化します。
   • 結果を保持する result を [True] で初期化します。
4. すべての頂点 i について、color[i] が -1(未訪問)なら dfs(i) を呼び出します。これにより連結成分ごとに探索が行われます。
5. 最後に result[0] を返します。

Pythonでの実装例

from collections import defaultdict

class Solution:
    def solve(self, arr):
        n = len(arr)
        # 隣接リストの構築(無向グラフなので双方向に登録)
        graph = [set() for i in range(n)]
        for i in range(n):
            for j in arr[i]:
                graph[j].add(i)
                graph[i].add(j)

        color = [-1] * n      # -1 = 未訪問
        result = [True]

        def dfs(source):
            for child in graph[source]:
                if color[child] != -1:
                    if color[child] == color[source]:
                        # 隣接頂点と同じ色 → 2部グラフではない
                        result[0] = False
                        return
                    continue
                # 隣接頂点に反対の色を割り当てて再帰探索
                color[child] = 1 - color[source]
                dfs(child)

        # 未訪問の頂点から DFS を開始(非連結グラフ対応)
        for i in range(n):
            if color[i] == -1:
                dfs(i)

        return result[0]

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

入力

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

出力

True

計算量

このアルゴリズムでは、各頂点と各辺が高々1回ずつ訪問されるため、時間計算量は O(V + E)(V: 頂点数、E: 辺数)、空間計算量も色管理リストと隣接リストの分だけ必要となり O(V + E) です。

まとめ

2部グラフの判定は、DFS(またはBFS)を使った2色塗り分け問題として定式化できます。隣接頂点に交互に異なる色を割り当てながら探索し、矛盾が発生した時点で2部グラフではないと判断します。この手法は、奇数長の閉路(奇サイクル)を含むグラフが2部グラフにならないという性質とも密接に関係しています。