C++ Programming Code Examples C++ > Computer Graphics Code Examples Program to Check if a Given Graph is Bipartite Program to Check if a Given Graph is Bipartite The problem takes a graph as input and checks whether it is Bipartite or not. 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. cpp-program-perform-greedy-coloring Set 1 = { 1, 3} and Set 2 = {2,4}, and hence the given graph is bipartite. cpp-program-check-bipartite-graph The above graph is not bipartite, as it does not fit the definition. - Use BFS to traverse all the vertices. - Take a vertex and colour it red. ('R') - Colour all its neighbour vertices as ('B'). (Blue = 'B' and Red = 'R') - Colour the next level vertices as ('R') and so, untill all vertices are coloured. - If at any step, we encounter contradicting colours, then the given graph to us is not bipartite!. - Hence, break and print "No" else print "Yes"; #include<bits/stdc++.h> using namespace std; int n,e,i,j; vector<vector<int> > graph; vector<int> color; bool vis[100011]; bool isBipartite() { color[0] = 1; // Mark colour as 1 for first vertex. queue <int> q; q.push(0); while (!q.empty()) { int temp = q.front(); q.pop(); for (i=0;i<n;i++) { if (graph[temp][i] && color[i] == -1) //if there is an edge, and colour is not assigned { color[i] = 1 - color[temp]; q.push(i); } else if (graph[temp][i] && color[i] == color[temp]) // if there is an edge and both vertices have same colours return 0; // graph is not bipartite } } return 1; } int main() { int x,y; cout<<"Enter number of vertices and edges respectively:"; cin>>n>>e; cout<<"\n"; graph.resize(n); color.resize(n,-1); memset(vis,0,sizeof(vis)); for(i=0;i<n;i++) graph[i].resize(n); for(i=0;i<e;i++) { cout<<"\nEnter edge vertices of edge "<<i+1<<" :"; cin>>x>>y; x--; y--; graph[x][y]=1; graph[y][x]=1; } if(isBipartite()) cout<<"Yes, The given graph is Bipartite.\n"; else cout<<"No, The given graoh is not Bipartite.\n"; return 0; }