2 部グラフ判定｜コードで実践

2 部グラフ判定

このレッスンで分かること

O(n + m)

2 部グラフ (bipartite graph) とは、ノードを 2 つのグループ A と B に分割でき、すべての辺がグループ間 (A -- B) にしか張られていないグラフのことです

身近な例としては、次のようなものがあります

2 部グラフ判定とは

無向グラフが 2 部グラフかどうかを BFS の彩色で判定する関数を実装する。本レッスンでは、2 部グラフ判定の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

2 部グラフ (bipartite graph) とは、ノードを 2 つのグループ A と B に分割でき、すべての辺がグループ間 (A -- B) にしか張られていないグラフのことです。同じグループ内のノード同士に辺がない、と言い換えてもよいです。

身近な例としては、次のようなものがあります。

ユーザー (集合 A) と購入した商品 (集合 B) の関係
学生 (A) と履修科目 (B) の対応
男女のペア関係 (理想的なケース)
試合のホームチームとアウェイチームの組み合わせ

本レッスンでは、無向グラフが 2 部グラフかどうかを 彩色アルゴリズム で判定します。2 色 (たとえば 0 と 1) で全ノードを塗り分けて、隣接ノードは必ず違う色になるなら 2 部グラフです。

2 部グラフ <=> 「2 色で塗り分けできる」<=> 「奇数長の閉路がない」。3 つの言い換えはすべて同値。

BFS で彩色する

手順は次のとおりです。

すべてのノードを未彩色 (color = -1) で初期化
未彩色のノードを見つけたら、それを色 0 で塗って BFS スタート
BFS で隣接ノード v を訪問するたび、color[v] がまだ未塗りなら自分と反対色を塗る
すでに塗られていて、それが自分と同色だったら 2 部グラフではない
すべての成分を処理し終わったら 2 部グラフ

diagram (will load when visible)

図のポイント (テキスト併記)

上の 4 ノードのサイクルは 0 - 1 - 0 - 1 と塗り分けられるので 2 部グラフ

上の 4 ノードのサイクルは 0 - 1 - 0 - 1 と塗り分けられるので 2 部グラフ。一方、3 ノードのサイクル (三角形) は奇数長なので必ず矛盾し、2 部グラフではありません。

Python での実装

Python

from collections import deque

def isBipartite(n, edges):
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    color = [-1] * n
    for start in range(n):
        if color[start] != -1:
            continue
        color[start] = 0
        queue = deque([start])
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    queue.append(v)
                elif color[v] == color[u]:
                    return False
    return True

ポイントは color[v] = 1 - color[u] で反対色を計算するところと、すでに塗られているときの color[v] == color[u] の衝突チェックです。

JavaScript での実装

JavaScript

function isBipartite(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
  }
  const color = new Array(n).fill(-1);
  for (let start = 0; start < n; start++) {
    if (color[start] !== -1) continue;
    color[start] = 0;
    const queue = [start];
    let head = 0;
    while (head < queue.length) {
      const u = queue[head++];
      for (const v of adj[u]) {
        if (color[v] === -1) {
          color[v] = 1 - color[u];
          queue.push(v);
        } else if (color[v] === color[u]) {
          return false;
        }
      }
    }
  }
  return true;
}

ロジックは Python とほぼ同じ。複数の連結成分があるかもしれないので、外側ループでまだ塗っていないノードを順に起点にする点に注意します。

奇数閉路と 2 部グラフ

「2 部グラフ <=> 奇数長閉路が存在しない」 という有名な定理があります。証明のアイデアは簡単で、奇数長の閉路を 2 色で塗ろうとすると最後で必ず矛盾するからです。彩色 BFS で color[v] == color[u] の衝突を見つけることが、まさに「奇数閉路の検出」になっています。

計算量

O(n + m)。BFS そのもの。1 回の探索で全成分を処理できます。

競技プログラミングでは「2 色で塗れるか」を聞かれたら 2 部グラフ判定だと思ってよい。マッチング問題の前提条件としても頻出。

よくある間違い

1 つ目は 複数連結成分 の見落とし。1 つの BFS だけだと到達できない成分があるかもしれないので、外側で start = 0..n-1 を回します。2 つ目は隣接ノードが未塗りかチェックする前に塗ってしまい、color[u] == color[v] の検査機会を逃すパターン。if color[v] == -1 の枝と elif をきちんと分けます。3 つ目は無向グラフを片方向にしか登録せず、辺の片側からしか塗らないバグです。

やってみよう

n=4, edges=[[0,1],[1,2],[2,3],[3,0]] (4 サイクル) で True。
n=3, edges=[[0,1],[1,2],[2,0]] (三角形) で False。
n=5, edges=[] (辺なし) で True (空集合と全集合に分割可能)。

2 部グラフ判定は「2 色塗り問題」の基本形。グラフ理論への入口として身につけておくと、後で マッチング や オイラー閉路 につながる。

よくある質問

Q. この内容は面接でよく聞かれますか？

A. コーディング面接の頻出範囲です。データ構造（リンクリスト・ツリー・グラフ）とアルゴリズム（DP・BFS/DFS）は IT 系大手の選考でほぼ確実に問われます。LeetCode の Top 100 にも該当問題が多数含まれます。

Q. 計算量と空間計算量はどっちを優先しますか？

A. 通常は時間計算量を優先し、空間が制約条件として明示されたら空間も考慮します。例えば「O(1) 空間で」と書かれていれば in-place アルゴリズム必須です。実務では時間 vs メモリのトレードオフを意識しつつ、ボトルネックを実測してから判断します。

Q. 問題が解けないときどう取り組めば良いですか？

A. まず小さな入力（n=3 程度）で手計算し、規則性を見つけます。次にナイーブ解（O(n²) でも可）を書き、最後に最適化します。いきなり最適解を狙うと手が止まりやすいので、段階的に進めるのが定石です。

次のレッスン

次は ダイクストラ法 — 重み付きグラフの最短経路 で、辺に重みがあるグラフで始点から各点への最短距離を求める方法を学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

2 部グラフ判定の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. 2 部グラフ判定とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

2 部グラフ判定