Implementation of bipartite graph using c++

 What a bipartite graph:-

 A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the parts of the graph.


Code:-

here we take a colour array in which we store the colour in form of 1 and 0 .if colour of parent and child is same then the graph is not a bipartite graph.

in the  code I use c^1 (c xor 1) that means if c have 1 then after xor operation it become 0 and if 0 then it become 1  

// Bipartite graph

#include<bits/stdc++.h>
using namespace std;
vector<int> arr[100];
int visited[100];
// array for colour
int col[100];

// function for dfs
bool dfs(int v,int c)
{
visited[v]=1;
col[v]=c;
for(int child:arr[v])
{
if(visited[child]==0)
{
auto f=dfs(child,c^1);
if(f==false)
{
return false;
}
}
else
{
if(col[v]==col[child])
return false;
}
}
return true;
}

//Driver function
int main()
{
int n,m;
printf(“Enter number vertex and number of edgesn”);
cin>>n>>m;
int a,b;
cout<<“Enter all the edges”<<endl;
for(int i=0;i<m;i++)
{
cin>>a>>b;
arr[a].push_back(b);
arr[b].push_back(a);
}
auto c=dfs(1,1);
if(c==false)
cout<<“Not a Bipartite graph”;
else
cout<<“Bipartite graph”;
return 0;
}

Output:-

for the graph

since is a bipartite graph. so let’s check by the code

Enter the number of vertex and edges
6 6
Enter all edges
1 2
1 6
2 3
3 4
4 5
5 6
Bipartite graph
 






Leave a Reply

Your email address will not be published.