# C++ Program to Perform Graph Coloring on Bipartite Graphs

This is a C++ Program to Perform Graph Coloring on Bipartite Graphs.

Problem Description

The problem takes a bipartite graph as input and outputs colours of the each vertex after coloring the vertices.

Bipartite Graph is a graph in which the set of vertices can be divided into two sets such that all vertex should be present in either set 1 or set 2 but not both, and there should no edge between vertices belonging to same set.

Example:

Set 1 = { 1, 3} and Set 2 = {2,4}

Problem Solution

1. Use BFS to traverse all the vertices.
2. Take a vertex and colour it red. (‘R’)
3. Colour all its neighbour vertices as (‘B’). (Blue = ‘B’ and Red = ‘R’)
4. Colour the next level vertices as (‘R’) and so, untill all vertices are coloured.

Program/Source Code

Here is source code of the C++ Program to Perform Graph Coloring on Bipartite Graphs. The program is successfully compiled and tested under Linux platform. The program output is also shown below.

```#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";
}
}```
Program Explanation

1. User must first enter the number of vertices, N, and then number of edges, E, in the graph.
2. It should be followed by E lines, denoting A and B, if there is an edge between A and B.
3. The graph is stored as adjacency list.
4. Then BFS is implemented using queue and colours are assigned to each vertex.

Runtime Test Cases
```
Case 1:
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

Case 2:
Enter number of vertices and edges respectively:4 4
'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 :2 3

Enter edge vertices of edge 3 :3 4

Enter edge vertices of edge 4 :1 4
1 1
2 0
3 1
4 0```

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

If you find any mistake above, kindly email to [email protected]