• • In this blog post we are going to learn Bipartite graph example. If the vertices of a graph can be divided into two independent sets U and V such that  every edge (u—-v) either u belongs to U and v belongs to V or u belongs to V and v belongs to U. Look at the below graph. The blue and red color dots are vertices of above graph and the line connecting the dots are edgesWe can see in the graph that no two dots of the same color are connected by a line(edge).

How to check whether a given graph is Bipartite or not

A graph is bipartite graph if it contains even number of cycles. Let us observe the above example graph (colored as blue and red dots) , it does not have odd length cycles.

Loot at below graph, the graph is not bipartite graph, because It is impossible to color a cycle graph with odd cycle using two colors. Now Let us check whether given below graph is bipartite or not. To check bipartite

(1) Take Two color value , for example RED and BLUE.

(2) Run Depth first search from any vertex (v).

(3) if a node is not visited ,color it with current color, make it visited

(4) if there is edge which starts with vertex v and ends with i, and if the color of vertex v and color of vertex i is same the graph is not bipartite.

(5) If condition 4 fails, do dfs from vertex i, with alternate color, like below

if( color == RED )
dfs(G,i,BLUE,visited);
else
dfs(G,i,RED,visited);

#include<stdio.h>
#include<stdbool.h>

#define ROW 7
#define COL 7

bool isbipartite = true;

#define RED 1
#define BLUE 2

void dfs(int G[ROW][COL],int vertex, int color,int visited[]);

int main()
{
// Adjacency matrix of graph
int   G[ROW][COL] = {{0, 1, 0, 0, 1, 0, 0},
{1, 0, 1, 0, 0, 1, 0},
{0, 1, 0, 1, 1, 0, 0},
{0, 0, 1, 0, 0, 0, 1},
{1, 0, 1, 0, 0, 1, 1},
{0, 1, 0, 0, 1, 0, 0},
{0, 0, 0, 1, 1, 0, 0}};

// makr all nodes not visited
int visited[ROW];
int i=0;
for(i=0;i<ROW;i++)
visited[i] = 0; // 0 means not visited
//  now color it with RED and BLUE
// if value of visited[i] is either RED or BLUE
// it denotes that it is visited node

// do dfs from 0th node,using recursive approach
dfs(G,0,RED,visited);

if( isbipartite)
printf("The Graph is bipartite \n");
else
printf("The Graph is not bipartite \n");

return 0;
}
void dfs(int G[ROW][COL],int vertex, int color,int visited[])
{
// if node is not visited
if( !visited[vertex] )
{
//make it visited and color it
visited[vertex] = color; //assign current color
}
int i=0;
for(i=0; i< ROW;i++)
{
// if there is edge between vertex and i
if( G[vertex][i] == 1)
{
// if color of vertex i is equal to
// color of v, that is current color
if( visited[i] == color )
{
isbipartite = false;
return;
}
if( !visited[i])
{
if( color == RED )
dfs(G,i,BLUE,visited);
else
dfs(G,i,RED,visited);

}
}

}

return;
}

http://codeforces.com/blog/entry/5048