C++でBFS（幅優先探索）を使ってグラフが2部グラフかどうかを判定する方法

2部グラフ（Bipartite Graph）とは、グラフ全体を2色だけで塗り分けできるグラフのことです。具体的には、隣接する頂点同士が必ず異なる色になるように着色でき、同じ集合に属する頂点はすべて同じ色で塗られるグラフを指します。

本記事では、BFS（幅優先探索：Breadth-First Search）を利用して、与えられたグラフが2部グラフであるかどうかを判定するC++プログラムを紹介します。

2部グラフとは

2部グラフとは、頂点集合を2つの集合に分割でき、すべての辺が必ず異なる集合に属する頂点同士を結ぶグラフです。これと等価な定義として、「2色で頂点を塗り分けたとき、隣接する頂点が常に異なる色になる」ことが挙げられます。

また、2部グラフには「奇数長の閉路（サイクル）を一切含まない」という重要な性質があります。この性質は、グラフの判定や応用問題を考える上で役立ちます。

判定アルゴリズムの手順

BFSを使った2部グラフの判定は、以下の手順で行います。

開始
　　関数 Bipartite():
　　1) 始点となる頂点に1つの色を割り当てる
　　2) その隣接頂点すべてに、最初とは別の色を割り当てる
　　3) さらにその隣接頂点には、最初の色を割り当てる
　　4) この操作を繰り返し、k = 2 の k彩色問題の制約を満たすように全頂点へ色を割り当てる
　　5) 色の割り当て中に、現在の頂点と同じ色で塗られた隣接頂点が見つかった場合、
　　　 グラフは2色で塗り分け不可能、すなわち2部グラフではないと判定する
終了

C++サンプルコード

#include <iostream>
#include <queue>
#define V 4
using namespace std;

bool Bipartite(int G[][V], int s) {
    int colorA[V];
    for (int i = 0; i < V; ++i)
        colorA[i] = -1;
    colorA[s] = 1; // 始点の頂点に色を割り当てる
    queue<int> q; // BFS探索用に頂点番号のキューを作成し、始点をエンキュー
    q.push(s);
    while (!q.empty()) {
        int w = q.front(); // 頂点をデキュー
        q.pop();
        for (int v = 0; v < V; ++v) { // 未着色の隣接頂点をすべて探す
            if (G[w][v] && colorA[v] == -1) { // wからvへの辺が存在し、vが未着色の場合
                colorA[v] = 1 - colorA[w]; // wの隣接頂点vに反対の色を割り当てる
                q.push(v);
            } else if (G[w][v] && colorA[v] == colorA[w]) { // vがwと同じ色の場合
                return false; // 2色で塗り分け不可 → 2部グラフではない
            }
        }
    }
    return true; // すべての隣接頂点を交互の色で塗り分けできた場合
}

int main() {
    int G[][V] = {{ 0, 1, 0, 0},
                  { 1, 0, 0, 0},
                  { 0, 0, 0, 1},
                  { 1, 0, 1, 0}};
    if (Bipartite(G, 0))
        cout << "The Graph is Bipartite" << endl;
    else
        cout << "The Graph is Not Bipartite" << endl;
    return 0;
}

実行結果

The Graph is Bipartite

コードの解説

このプログラムでは、始点からBFSを実行しながら、各頂点に交互に色（1 と 0）を割り当てていきます。隣接行列 G を走査し、まだ着色されていない隣接頂点には現在の頂点と逆の色を設定してキューに追加します。

一方で、すでに着色済みの隣接頂点が現在の頂点と同じ色だった場合は、2色での塗り分けに失敗したことを意味するため、即座に false を返します。すべての頂点を矛盾なく着色できれば true を返し、そのグラフは2部グラフであると判定されます。

計算量について見てみましょう。隣接行列を使用しているため、時間計算量は O(V²) となります。グラフが疎な場合は、隣接リストを使用することで O(V + E) まで改善できます。