C++で2部グラフのグラフ彩色を行うプログラムの解説

2部グラフ（Bipartite Graph）とは、グラフ全体を2色だけで彩色できるグラフのことです。つまり、頂点を2つの集合に分け、同じ集合内の頂点にはすべて同じ色が割り当てられます。この記事では、2部グラフを入力として受け取り、各頂点に彩色を行った結果を出力するC++プログラムを紹介します。

アルゴリズム

Begin
   幅優先探索（BFS）を使ってすべての頂点を走査します。
   1つの頂点を選び、黄色に塗ります。
   その隣接する頂点をすべて青色に塗ります。
   次のレベルの頂点は黄色に塗り、これを全頂点が彩色されるまで繰り返します。
End.

サンプルコード

#include<bits/stdc++.h>
using namespace std;
int n, e, i, j;
vector<vector<int> > g;
vector<int> color;
bool v[11101];
void c(int node,int n) {
    queue<int> q;
    if(v[node])
      return;
    color[node]=n;
    v[node]=1;
    for(i=0;i<n;i++) {
      if(!v[g[node][i]]) {
         q.push(g[node][i]);
      }
    }
    while(!q.empty()) {
      c(q.front(),(n+1)%2);
      q.pop();
    }
    return;
}
int main() {
    int a,b;
    cout<<"Enter number of vertices and edges respectively:";
    cin>>n>>e;
    cout<<"'Y' is for Yellow Colour and 'B' is for Blue Colour.";
    cout<<"\n";
    g.resize(n);
    color.resize(n);
    memset(v,0,sizeof(v));
    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);
    }
    c(0,1);
    for(i=0;i<n;i++) {
      if(color[i])
         cout<<i+1<<" "<<'Y'<<"\n";
      else
         cout<<i+1<<" "<<'B'<<"\n";
   }
}

出力結果

Enter number of vertices and edges respectively:4 3
'Y' is for Yellow Colour and 'B' is for Blue Colour.

Enter edge vertices of edge 1 :1 2
Enter edge vertices of edge 2 :3 2
Enter edge vertices of edge 3 :4 2
1 Y
2 B
3 B
4 B