C++のDFS（深さ優先探索）でグラフが2部グラフかどうかを判定する方法

2部グラフとは

2部グラフ（Bipartite Graph）とは、グラフのすべての頂点をちょうど2つの色で塗り分けられるグラフのことです。このとき、同じ色を持つ頂点同士は互いに隣接しないという条件を満たす必要があります。言い換えると、「隣接する頂点は必ず異なる色になる」という性質を満たすグラフが2部グラフです。

本記事では、深さ優先探索（DFS：Depth First Search）を用いて、与えられたグラフが2部グラフであるかどうかを判定するC++プログラムを解説します。

アルゴリズム

DFSを利用した2部グラフの判定は、以下の手順で行われます。

1. 各ノードに対して0または1の値を格納する配列 color[] を用意します。0と1は互いに反対の色を表します。
2. 任意のノードからDFS関数を呼び出します。
3. ノード w がまだ訪問されていない場合、親ノード v の色と反対の色 !color[v] を color[w] に割り当てます。その後、w に接続されたノードを訪問するために、再帰的にDFSを呼び出します。
4. 探索の過程で、隣接する2つの頂点に同じ色が割り当てられていることが判明した場合、そのグラフは2部グラフではありません。

サンプルコード

#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 を追加
}
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);
    vector<int> color(M + 1); // 頂点を2色で塗り分けるための配列
    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」で構成される奇数長の閉路（三角形のサイクル）が含まれており、隣接する頂点を2色で塗り分けることができないため、「2部グラフではない」と判定されます。一般に、グラフが2部グラフである必要十分条件は、奇数長の閉路を含まないことです。

計算量について

このアルゴリズムの時間計算量は O(V + E)、空間計算量は O(V) です（V は頂点数、E は辺数）。DFSにより各頂点と各辺を高々1回ずつ処理するだけで判定が完了するため、非常に効率的な手法と言えます。