双分图图着色的 C++ 程序

双分图是如果可以通过两种颜色对图进行着色时的一种图，即用同一种颜色对一个集合中的顶点进行着色。本程序以双分图作为输入，并在对顶点进行着色后输出每个顶点的颜色。

算法

Begin
   BFS algorithm is used to traverse all the vertices.
   Take a vertex and colour it yellow.
   Colour all its neighbour vertices as blue.
   Colour the next level vertices as yellow and so, until all vertices are coloured.
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

Vrundesha Joshi

更新于： 2019 年 7 月 30 日

367 次查看

开启你的 事业

完成本课程可获得认证

立即开始