C++ Program to Perform Graph Coloring on Bipartite Graphs - Computer Programming

# Computer Programming

C C++ Java Python Perl Programs Examples with Output -useful for Schools & College Students

## Tuesday, September 26, 2017

Write a C++ Program to Perform Graph Coloring on Bipartite Graphs

Program:
#include<bits/stdc++.h>

using namespace std;

int n,e,i,j;
vector<vector<int> > graph;
vector<int> color;
bool vis[100011];

void colour(int node,int num)
{
queue<int> q;
if(vis[node])
return;
color[node]=num;
vis[node]=1;
for(i=0;i<n;i++)
{
if(!vis[graph[node][i]])
{
q.push(graph[node][i]);
}
}
while(!q.empty())
{
colour(q.front(),(num+1)%2);
q.pop();
}
return;
}

int main()
{
int x,y;
cout<<"Enter number of vertices and edges respectively:";
cin>>n>>e;
cout<<"'R' is for Red Colour and 'B' is for Blue Colour.";
cout<<"\n";
graph.resize(n);
color.resize(n);
memset(vis,0,sizeof(vis));
for(i=0;i<e;i++)
{
cout<<"\nEnter edge vertices of edge "<<i+1<<" :";
cin>>x>>y;
x--; y--;
graph[x].push_back(y);
graph[y].push_back(x);
}
colour(0,1);
for(i=0;i<n;i++)
{
if(color[i])
cout<<i+1<<" "<<'R'<<"\n";
else
cout<<i+1<<" "<<'B'<<"\n";
}
}

Output:
Enter number of vertices and edges respectively:6 5
'R' is for Red Colour and 'B' is for Blue Colour.

Enter edge vertices of edge 1 :1 2

Enter edge vertices of edge 2 :1 3

Enter edge vertices of edge 3 :4 5

Enter edge vertices of edge 4 :4 6

Enter edge vertices of edge 5 :2 4
1 R
2 B
3 B
4 R
5 B

6 B