C++で実装するグラフの辺彩色（エッジカラーリング）プログラム

この記事では、グラフの辺彩色（エッジカラーリング）を行うC++プログラムを紹介します。辺彩色とは、グラフのすべての辺に色を割り当てる際に、同じ頂点に接続する（隣接する）2つの辺が同じ色にならないようにする問題です。

アルゴリズムの全体像

本プログラムでは、キューを用いた幅優先探索（BFS）によって頂点を順に訪問しながら、各辺に適切な色を割り当てていきます。大まかな流れは次のとおりです。

Begin
    1. グラフの頂点数 n と辺数 e を入力として受け取る。
    2. グラフを隣接リストとして格納する。
    3. キューを使ったBFSを実装し、各辺に色を割り当てる。
End

処理のポイント

• 訪問管理： 配列 v を使って、すでに処理済みの頂点を二度と訪問しないようにします。
• 使用済み色の記録： 現在の頂点に接続する辺のうち、すでに色が確定しているものを集合 vertex_colored に登録します。
• 色の選択： まだ色が付いていない辺には、vertex_colored に存在しない最小の色番号を順に割り当てます。これにより、同一頂点上の辺同士が必ず異なる色になります。
• BFSによる展開： 未訪問の隣接頂点をキューに追加し、順番に処理を進めます。

C++サンプルコード

#include<bits/stdc++.h>
using namespace std;
int n, e, i, j;
vector<vector<pair<int, int> > > g;
vector<int> color;
bool v[111001];
void col(int n) {
    queue<int> q;
    int c = 0;
    set<int> vertex_colored;
    if(v[n])
       return;
       v[n] = 1;
    for(i = 0;i<g[n].size();i++) {
       if(color[g[n][i].second]!=-1) {
          vertex_colored.insert(color[g[n][i].second]);
       }
    }
    for(i = 0;i<g[n].size();i++) {
       if(!v[g[n][i].first]) {
          q.push(g[n][i].first);
       }
       if(color[g[n][i].second]==-1) {
          while(vertex_colored.find(c)!=vertex_colored.end())
             c++;
             color[g[n][i].second] = c;
             vertex_colored.insert(c);
             c++;
       }
    }
    while(!q.empty()) {
       int temp = q.front();
       q.pop();
       col(temp);
    }
    return;
}
int main() {
    int u,w;
    set<int> empty;
    cout<<"Enter number of vertices and edges respectively:";
    cin>>n>>e;
    cout<<"\n";
    g.resize(n); //number of vertices
    color.resize(e,-1); //number of edges
    memset(v,0,sizeof(v));
    for(i = 0;i<e;i++) {
       cout<<"\nEnter edge vertices of edge "<<i+1<<" :"<<"\n";
       cin>>u>>w;
       u--; w--;
       g[u].push_back(make_pair(w,i));
       g[w].push_back(make_pair(u,i));
    }
    col(0);
    for(i = 0;i<e;i++) {
       cout<<"Edge "<<i+1<<" is coloured with colour "<<color[i]+1
       << "\n";
    }
}

実行例

頂点数 4、辺数 5 のグラフを入力として与えた場合の実行結果です。

Enter number of vertices and edges respectively:4 5
Enter edge vertices of edge 1 :1 2
Enter edge vertices of edge 2 :2 3
Enter edge vertices of edge 3 :1 1
Enter edge vertices of edge 4 :3 4
Enter edge vertices of edge 5 :1 4
Edge 1 is coloured with colour 1
Edge 2 is coloured with colour 2
Edge 3 is coloured with colour 2
Edge 4 is coloured with colour 1
Edge 5 is coloured with colour 3

結果の確認

このグラフでは、頂点1に辺1・辺3・辺5が接続しており、それぞれ色1・色2・色3と互いに異なる色が割り当てられています。他の頂点についても、接続する辺同士が同じ色になっていないことが確認できます。なお、辺3は自己ループ（頂点1から頂点1への辺）ですが、この場合も他の辺と重複しない色が正しく選択されています。

このように、BFSと貪欲法を組み合わせた色の割り当てを行うことで、隣接する辺が同じ色を持たない辺彩色をシンプルに実現できます。