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.