DFSを使用してグラフが2部グラフかどうかを判定するC++プログラム

2部グラフ（バイパータイトグラフ）とは、グラフ全体を2色で塗り分けることができるグラフのことです。つまり、隣接する2つの頂点が必ず異なる色になるように頂点を着色できるグラフを指します。本記事では、DFS（深さ優先探索）を用いて、与えられたグラフが2部グラフかどうかを判定するC++プログラムを解説します。

2部グラフとは

2部グラフとは、頂点集合を2つのグループに分割し、すべての辺が必ず異なるグループに属する頂点同士を結ぶようなグラフです。この性質があるため、「隣接する頂点同士を異なる色で塗る」という操作をグラフ全体に適用できるかどうかを調べることで、2部グラフの判定が可能になります。

アルゴリズム

DFSを用いた2部グラフの判定は、次の手順で行います。

1. 各ノードの色（0または1）を記録する配列 color[] を用意します。
2. 任意のノードからDFSを開始します。
3. 隣接ノードwが未訪問の場合、現在のノードの色を反転した値（!color[v]）を color[w] に代入し、さらにwに接続されたノードへ向けてDFSを再帰的に呼び出します。
4. 探索の途中で、隣接する2つの頂点に同じ色が割り当てられていることが判明した場合、そのグラフは2部グラフではありません。
5. すべての頂点を矛盾なく塗り分けられれば、そのグラフは2部グラフです。

C++プログラム例

#include<iostream>
#include <bits/stdc++.h>
using namespace std;

// グラフに辺を追加する関数
void addEd(vector<int> adj[], int w, int v) {
    adj[w].push_back(v); // wの隣接リストにvを追加
    adj[v].push_back(w); // vの隣接リストにwを追加
}

// DFSにより2部グラフかどうかを判定する関数
bool Bipartite(vector<int> adj[], int v,
    vector<bool>& visited, vector<int>& color) {
    for (int w : adj[v]) {
        // 頂点wが未探索の場合
        if (visited[w] == false) {
            // 現在の頂点を訪問済みとしてマーク
            visited[w] = true;
            // 親の頂点とは逆の色を設定
            color[w] = !color[v];
            if (!Bipartite(adj, w, visited, color))
                return false;
        }
        // 隣接する2頂点が同じ色の場合、グラフは2部グラフではない
        else if (color[w] == color[v])
            return false;
    }
    return true;
}

int main() {
    int M = 6;
    vector<int> adj[M + 1];
    // ノードが発見済みかどうかを管理する配列
    vector<bool> visited(M + 1);
    // グラフの頂点を2色で塗り分けるための配列
    vector<int> color(M + 1);

    addEd(adj, 3, 2);
    addEd(adj, 1, 4);
    addEd(adj, 2, 1);
    addEd(adj, 5, 3);
    addEd(adj, 6, 2);
    addEd(adj, 3, 1);

    visited[1] = true;
    color[1] = 0;

    if (Bipartite(adj, 1, visited, color)) {
        cout << "Graph is Bipartite";
    } else {
        cout << "Graph is not Bipartite";
    }
    return 0;
}

実行結果

Graph is not Bipartite

このサンプルグラフには、奇数長の閉路（例：1 → 2 → 3 → 1）が含まれています。2部グラフは奇数長の閉路を含むことができないため、このグラフは2部グラフではないと判定されます。

コードのポイント

• addEd() 関数は無向グラフに辺を追加するため、両方向の隣接リストに頂点を登録しています。
• Bipartite() 関数は再帰的なDFSとして実装されており、未訪問の隣接頂点には親と逆の色を割り当てます。
• すでに訪問済みの隣接頂点と同じ色だった場合は即座に false を返し、探索を打ち切ります。
• 非連結グラフの場合は、すべての連結成分に対して判定を実行する必要があります。

計算量

頂点数をV、辺数をEとすると、このアルゴリズムの時間計算量は O(V + E) です。各頂点と各辺を高々1回ずつ処理するため、比較的大きなグラフでも効率的に動作します。また、再帰呼び出しの深さに応じて、最大 O(V) のスタック領域が必要になります。