C++で実装する貪欲法（グリーディ）によるグラフ彩色プログラム

グラフ理論におけるグラフ彩色問題とは、辺で直接つながっている（隣接する）頂点同士が同じ色にならないように、すべての頂点へ色を割り当てる古典的な問題です。本記事では、その代表的な解法である貪欲法（グリーディ法）を使ってグラフ彩色を実行するC++プログラムを、アルゴリズムの手順・サンプルコード・実行結果とあわせてわかりやすく解説します。

貪欲法による彩色の基本的な考え方

貪欲法は、各頂点を順番に処理し、「その時点で隣接頂点がまだ使っていない色のうち、最も小さい番号の色」を割り当てていくシンプルな手法です。常に最小の色数になることを保証するものではありませんが、計算量が少なく実装も容易なため、実用的な場面で広く利用されています。

アルゴリズムの手順

開始
　　頂点数と辺数を入力として受け取る。
　　頂点に色を割り当てる関数 greedyColoring() を作成する：
　　A) 最初の頂点に最初の色を割り当てる。
　　B) 残りの頂点の色を未割り当て状態（-1）で初期化する。
　　C) 利用可能な色を記録するための一時配列を用意する。
　　D) 残りの頂点に対して、隣接頂点が使用していない最小の色を割り当てる。
　　結果（各頂点の色）を出力する。
終了

サンプルコード

以下は、隣接リスト形式のグラフを受け取り、貪欲法で彩色を行うC++の完全な実装例です。

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int n,e,i,j;
vector<vector<int> > g;
vector<int> col;
bool visit[1001];
void greedyColoring()
{
   col[0] = 0;
   for (i=1;i<n;i++)
   col[i] = -1;
   bool unuse[n];
   for (i=0;i<n;i++)
   unuse[i]=0;
   for (i = 1; i < n; i++)
   {
      for (j=0;j<g[i].size();j++)
      if (col[g[i][j]] != -1)
      unuse[col[g[i][j]]] = true;
      int cr;
      for (cr=0;cr<n;cr++)
         if (unuse[cr] == false)
    break;
      col[i] = cr;
      for (j=0;j<g[i].size();j++)
      if (col[g[i][j]] != -1)
      unuse[col[g[i][j]]] = false;
   }
}
int main()
{
   int a,b;
   cout<<"Enter number of vertices and edges respectively:";
   cin>>n>>e;
   cout<<"\n";
   g.resize(n);
   col.resize(n);
   memset(visit,0,sizeof(visit));
   for(i=0;i<e;i++)
   {
      cout<<"\nEnter edge vertices of edge "<<i+1<<" :";
      cin>>a>>b;
      a--; b--;
      g[a].push_back(b);
      g[b].push_back(a);
   }
   greedyColoring();
   for(i=0;i<n;i++)
   {
      cout<<"Vertex "<<i+1<<" is coloured with "<<col[i]+1<<"\n";
   }
}

コードのポイント

• グラフは隣接リスト（vector<vector<int>）で管理され、無向グラフとして両方向の辺を登録しています。
• 配列 col には各頂点の色番号を保存し、未割り当ての状態は -1 で表します。
• 一時配列 unuse を使って「すでに隣接頂点が使用している色」をマークし、先頭から走査して最初に空いている色を採用します。
• 処理後に unuse のフラグを元に戻すことで、次の頂点の判定を正しく行えるようにしています。

実行例（出力結果）

7つの頂点と6つの辺からなるグラフを入力した場合の実行例は以下のとおりです。

Enter number of vertices and edges respectively:7
6
Enter edge vertices of edge 1 :4 5
Enter edge vertices of edge 2 :2 3
Enter edge vertices of edge 3 :1 1
Enter edge vertices of edge 4 :1 4
Enter edge vertices of edge 5 :6 7
Enter edge vertices of edge 6 :2 2
Vertex 1 is coloured with 1
Vertex 2 is coloured with 1
Vertex 3 is coloured with 2
Vertex 4 is coloured with 2
Vertex 5 is coloured with 1
Vertex 6 is coloured with 1
Vertex 7 is coloured with 2

この結果から、どの頂点にも隣接する頂点と重ならない色が割り当てられていることが確認できます。このように貪欲法を使えば、少ない計算量で効率的にグラフ彩色の近似解を求めることが可能です。