2色アルゴリズムで二部グラフを判定するC++プログラム

二部グラフとは、頂点集合を2つのグループに分割し、同一グループ内に辺が存在しないグラフのことです。これは、グラフの頂点を2色で塗り分けられる（隣接する頂点が異なる色になる）ことと同義です。本記事では、バックトラック法に基づく2色アルゴリズムを用いて、与えられたグラフが二部グラフかどうかを判定するC++プログラムを解説します。

アルゴリズムの概要

このアルゴリズムは、頂点を順番に処理し、各頂点に色（1または2）を割り当てていきます。割り当ての際、隣接する頂点と同じ色にならないかをチェックします（isSafe関数）。全頂点に矛盾なく色を割り当てられれば二部グラフ、どこかで矛盾が生じれば二部グラフではありません。

主要な関数と疑似コード

1. isSafe 関数（安全性チェック）

頂点 v に色 c を割り当てた際、隣接頂点と色が衝突しないか確認します。

isSafe(v, graph, color[], c):
    for i = 0 to V-1:
        if graph[v][i] == true かつ color[i] == c:
            return false  // 隣接頂点が同色 → 不正
    return true           // 安全

2. graphColoringUtil 関数（再帰的な色割り当て）

頂点 v から順に色を試行し、解が見つかれば true を返します。

graphColoringUtil(graph, k, color[], v):
    if v == V:
        return true  // 全頂点に割り当て完了

    for c = 1 to k:  // k=2 の場合、色1と2を試す
        if isSafe(v, graph, color, c):
            color[v] = c
            if graphColoringUtil(graph, k, color, v+1) == true:
                return true
            color[v] = 0  // バックトラック（色を戻す）
    return false

3. graphColoring 関数（エントリーポイント）

色配列を初期化し、再帰関数を呼び出します。

graphColoring(graph, k):
    color[0...V-1] = {0}
    if graphColoringUtil(graph, k, color, 0) == false:
        return false
    return true

C++ 実装例

以下はコンパイル・実行可能な完全なコードです。隣接行列でグラフを表現し、2色で塗り分け可能か判定します。

#include <iostream>
#include <vector>

using namespace std;

const int V = 4; // 頂点数

// 頂点 v に色 c を割り当てても安全かチェック
bool isSafe(int v, bool graph[V][V], vector& color, int c) {
    for (int i = 0; i < V; i++) {
        if (graph[v][i] && color[i] == c)
            return false;
    }
    return true;
}

// 再帰的に色を割り当てる
bool graphColoringUtil(bool graph[V][V], int k, vector& color, int v) {
    if (v == V)
        return true;

    for (int c = 1; c <= k; c++) {
        if (isSafe(v, graph, color, c)) {
            color[v] = c;
            if (graphColoringUtil(graph, k, color, v + 1))
                return true;
            color[v] = 0; // バックトラック
        }
    }
    return false;
}

// メインの判定関数
bool isBipartite(bool graph[V][V]) {
    vector color(V, 0);
    if (graphColoringUtil(graph, 2, color, 0) == false) {
        return false;
    }
    // 確認用：割り当てられた色を表示
    cout << "割り当てられた色: ";
    for (int c : color) cout << c << " ";
    cout << endl;
    return true;
}

int main() {
    // 隣接行列の定義 (例: 4頂点のサイクルグラフ C4 - 二部グラフ)
    bool graph[V][V] = {
        {0, 1, 0, 1},
        {1, 0, 1, 0},
        {0, 1, 0, 1},
        {1, 0, 1, 0}
    };

    // 非二部グラフの例 (三角形 C3)
    // bool graph[V][V] = {
    //     {0, 1, 1, 0},
    //     {1, 0, 1, 0},
    //     {1, 1, 0, 0},
    //     {0, 0, 0, 0}
    // };

    if (isBipartite(graph))
        cout << "The graph is Bipartite (二部グラフです)" << endl;
    else
        cout << "The graph is NOT Bipartite (二部グラフではありません)" << endl;

    return 0;
}

実行結果

割り当てられた色: 1 2 1 2
The graph is Bipartite (二部グラフです)

補足と計算量

• 時間計算量: 最悪ケースで O(2^V) ですが、二部グラフ判定であれば BFS/DFS を用いた O(V+E) の線形時間アルゴリズムが一般的です。このバックトラック法は「m色塗り分け問題」の一般解として理解するのに適しています。
• 用途: スケジューリング問題、レジスタ割り当て、地図の彩色など、制約充足問題の基礎となります。