C++で解く支配集合問題：貪欲法によるプログラム実装と解説

これは、グラフ理論における支配集合問題(Dominating Set Problem)を解決するためのC++プログラムです。支配集合とは、グラフの頂点部分集合のうち、集合に含まれないすべての頂点が集合内のいずれかの頂点と隣接しているようなものを指します。本記事では、貪欲法を用いたシンプルな実装例をわかりやすく紹介します。

アルゴリズム

本プログラムで採用している貪欲法の流れは以下の通りです。

Begin
    頂点の数と辺の数、および各辺の端点を入力として受け取る。
    関数 dominant():
        ベクター Set を宣言する。
        頂点 X と Y をつなぐ任意の辺 e をグラフから選ぶ。
        X と Y のうち一方の頂点を集合 s に追加する。
        X に接続されているすべての辺を削除する。
End

プログラム例

#include<bits/stdc++.h>
using namespace std;
vector<vector<int> > g;
bool visit[10001];
int i,j;
vector<int> dominant(int v,int e) {
    vector<int> Set;
    // 頂点XとYをつなぐ任意の辺eを選ぶ
    for(i=0;i<v;i++) {
        if(!visit[i]) {
            Set.push_back(i); // 頂点を集合に追加
            visit[i]=true;
            for(j=0;j<(int)g[i].size();j++) {
                if(!visit[g[i][j]]) {
                    visit[g[i][j]]=true;
                    break;
                }
            }
        }
    }
    return Set;
}
int main() {
    int v,e,a,b;
    cout<<"頂点の数を入力してください:";
    cin>>v;
    cout<<"辺の数を入力してください:";
    cin>>e;
    g.resize(v);
    memset(visit,0,sizeof(visit)); // 配列の全要素を0(未訪問)に初期化
    for(i=0;i<e;i++) {
        cout<<"辺 "<<i+1<<" の端点を入力してください: ";
        cin>>a>>b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> Set = dominant(v,e);
    cout<<"支配集合は次の通りです:\n";
    for(i=0;i<(int)Set.size();i++)
        cout<<Set[i]+1<<" ";
    return 0;
}

出力

頂点の数を入力してください:7
辺の数を入力してください:6
辺 1 の端点を入力してください: 1 2
辺 2 の端点を入力してください: 2 2
辺 3 の端点を入力してください: 3 4
辺 4 の端点を入力してください: 4 5
辺 5 の端点を入力してください: 6 7
辺 6 の端点を入力してください: 4 5
支配集合は次の通りです:
1 3 5 6

プログラムの解説

グラフは隣接リスト(vector<vector<int>>)として表現されています。関数 dominant() は、未訪問の頂点を見つけるたびにその頂点を解の集合へ追加し、続いて隣接する頂点を訪問済みとしてマークしていきます。この処理により、すべての頂点が「自身が集合に含まれる」か「集合内の頂点に隣接している」かのいずれかの状態となり、支配集合の条件が満たされます。

計算量は O(V + E) と効率的で、頂点数や辺数が多いグラフにも対応できます。ただし、支配集合問題はNP困難であることが知られているため、この貪欲法が返すのは近似解であり、必ずしも最小の支配集合を保証するものではない点には注意が必要です。厳密な最小解が必要な場合には、指数時間の探索を伴う手法を検討する必要があります。