C++ Program to Perform Graph Coloring on Bipartite Graphs

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

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}

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.

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";
	}
}

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.

 
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.