Posted on by Kalkicode
Code Graph

# Check if a graph is bipartite or not

In graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets such that every edge connects a vertex in one set to a vertex in the other set. In other words, a bipartite graph is a graph that can be colored with two colors such that no two adjacent vertices have the same color.

To check if a graph is bipartite or not, we can use the following algorithm:

1. Choose an arbitrary vertex v in the graph and color it with color 1.
2. Color all its neighbors with color 2.
3. Color all the neighbors of vertices with color 2 with color 1.
4. Repeat step 3 until all vertices are colored or a conflict is found (i.e., a vertex has two adjacent vertices with the same color).

If all vertices can be successfully colored without conflicts, then the graph is bipartite. Otherwise, the graph is not bipartite.

Alternatively, we can use the concept of graph coloring and check if the graph can be colored with two colors such that no two adjacent vertices have the same color. This can be done using a graph coloring algorithm such as the greedy algorithm or the backtracking algorithm. If the graph can be colored with two colors, then it is bipartite. Otherwise, it is not bipartite.

## Program List

``````//C Program
//Check whether a given graph is Bipartite or not
//Using DFS
#include<stdio.h>
#include<stdlib.h>

struct AjlistNode
{
int vId;//Vertices id
struct AjlistNode*next;
};

struct Graph
{
int data; //node key value
struct AjlistNode*next;
};

int size; //number of nodes

//set node key value
void setData(struct Graph*node)
{
if(node!=NULL && size>0)
{
int index=0;
for(index;index<size;index++)
{
//set vertic node data
node[index].data=index;//set node key
//Initial no AjlistNode
//set NULL Value
node[index].next=NULL;
}

}else
{
printf("Vertic Node is Empty");
}
}
void connectEdge(struct Graph*node, int V ,int E)
{

struct AjlistNode *newEdge=(struct AjlistNode*)malloc(
sizeof(struct AjlistNode)
);

if(newEdge!=NULL)
{

newEdge->next=NULL;
newEdge->vId=E;

struct AjlistNode *temp=node[V].next;

if(temp==NULL)
{
node[V].next=newEdge;

}else
{
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=newEdge;
}
}else
{
printf("\n Memory overflow");
exit(0);
}
}
//Add Edge from Two given Nodes
void addEdge(struct Graph*node, int V ,int E)
{

if(V<size && E <size)
{
connectEdge(node,V,E);
connectEdge(node,E,V);
}else
{
//not valid Vertices
printf("Invalid Node Vertices %d  %d", V,E);
}
}
void printGraph(struct Graph*node)
{
if(node!=NULL)
{
struct AjlistNode *temp=NULL;
for(int index=0;index<size;index++)
{
printf("\n Adjacency list of vertex %d  :",index);
temp=node[index].next;
while(temp!=NULL)
{
//temp->vId is graph node vertices
//in this case temp->vId is same as
//node[temp->vId].data

printf("  %d",node[temp->vId].data);
temp=temp->next;
}
}
}else
{
printf("Empty Graph");
}
}

//Method which is check a given undirected graph is an Bipartite or not?
//same to DFS
void bipartite(int position,
int *visit,
struct Graph*node,
int color,
int *result)
{
//Base case
if(*result==0) return;

if(visit[position]!=-1)
{
if(visit[position]!=color)
{
*result=0;
//when need more then two color
visit[position]=2;
}
return;

}else
{

visit[position]=color;

struct AjlistNode *temp=node[position].next;

while(temp!=NULL)
{
bipartite(temp->vId,visit,node,!color,result);
temp=temp->next;
}
}
}

int main()
{
//number of nodes
size=7;

struct Graph*node=NULL;

node=(struct Graph*)malloc(sizeof(struct Graph)*size);

if(node==NULL)
{
printf("\n Memory overflow");

}
else
{

int visit[size],result=1;

for (int i = 0; i < size; ++i)
{
//set -1 because 0 and 1 will used to color
visit[i]=-1;
}

//First set node keys
setData(node);

//Connected two node with Edges

//Display all nodes in adjacency list
printGraph(node);

bipartite(0,visit,node,0,&result);

if(result==1)
{
//Check each vertex are visiting or not
for (int i = 0; i < size; ++i)
{
if(visit[i]==-1)
{
result=0;
break;
}
}
}
printf("\n  ---------------");
if(result==1)
{
printf("\n This is a Bipartite Graph \n");

}
else
{
//There are many posiblity
//Two adjacent nodes are have same color
//Not visiting all nodes by given source
printf("\n This is not a Bipartite Graph\n");
}
printf(" ---------------\n");
//Tracing the result by node color
//That is optional
for (int i = 0; i < size; ++i)
{
//0 and 1 are indicates color
//if -1 , so that means node are not visit
printf(" Node [%d] -> color : %d\n",i,visit[i] );

}
}
return 0;
}``````

#### Output

`````` Adjacency list of vertex 0  :  1
Adjacency list of vertex 1  :  0  4  5
Adjacency list of vertex 2  :  4  6
Adjacency list of vertex 3  :  5
Adjacency list of vertex 4  :  1  2
Adjacency list of vertex 5  :  1  3
Adjacency list of vertex 6  :  2
---------------
This is a Bipartite Graph
---------------
Node [0] -> color : 0
Node [1] -> color : 1
Node [2] -> color : 1
Node [3] -> color : 1
Node [4] -> color : 0
Node [5] -> color : 0
Node [6] -> color : 0
``````
``````//C++ program
//Check whether a given graph is Bipartite or not
//Using DFS
#include <iostream>
using namespace std;

struct AjlistNode
{
int vId;//Vertices id
struct AjlistNode*next;
};

struct Vertices
{
int data; //node key value
struct AjlistNode*next;
};

class Graph
{
Vertices *node;
int size;//number of
public:
Graph(int);
void setData();
void printGraph();
void connect(int  ,int );
void bipartite();
void is_bipartite(int,int *,int ,int *);

};
Graph::Graph(int size)
{
this->size = size;
//set number of nodes
node = new Vertices[size];
}
//set node key value
void Graph:: setData()
{
if(node!=NULL)
{
int index=0;

for(index;index<size;index++)
{
//set vertic node data
node[index].data=index;//set node key
//Initial no AjlistNode
//set NULL Value
node[index].next=NULL;
}
}
else
{
cout<<"Vertic Node is Empty"<<endl;
}
}
//Add Edge from Two given Nodes
void Graph ::connect(int start ,int end)
{
//add edge form start to end
//start and end is Node location
AjlistNode *newEdge=new AjlistNode;

if(newEdge!=NULL)
{

newEdge->next = NULL;
newEdge->vId = end;

AjlistNode *temp=node[start].next;

if(temp==NULL)
{
node[start].next=newEdge;
}else
{
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=newEdge;
}
}

}

void Graph ::  addEdge(int V ,int E)
{
//add edge form V to E
//V and E is Node location
if(V<size && E <size)
{
connect(V,E);
if(V!=E)
{
connect(E,V);
}

}else
{
//not valid Vertices
cout<<"Invalid Node Vertices "<< V<<" "<<E;
}
}

void Graph:: printGraph()
{
if(node!=NULL)
{
AjlistNode *temp=NULL;
for(int index=0; index < size; index++)
{
cout<<"\n Adjacency list of vertex "<<index<<" :";
temp=node[index].next;
while(temp!=NULL)
{
//temp->vId is graph node vertices
//in this case temp->vId is same as
//node[temp->vId].data

cout<<" "<<node[temp->vId].data;
temp=temp->next;
}
}
}else
{
cout<<"Empty Graph"<<endl;
}
}
//Method which is check a given undirected graph is an Bipartite or not?
//same to DFS
void Graph:: is_bipartite(int position,
int *visit,
int color,
int *result)
{
//Base case
if(*result==0) return;

if(visit[position]!=-1)
{
if(visit[position]!=color)
{
*result=0;
//when need more then two color
visit[position]=2;
}
return;

}else
{

visit[position]=color;

AjlistNode *temp=node[position].next;

while(temp!=NULL)
{
is_bipartite(temp->vId,visit,!color,result);
temp=temp->next;
}
}
}

void Graph:: bipartite()
{
int visit[size] , result = 1 ;

for ( int i = 0 ;  i < size ;  ++i)
{
//set -1 because 0 and 1 will used to color
visit[i] = -1 ;
}

is_bipartite( 0 , visit , 0 , &result) ;

if (result == 1)
{
//Check each vertex are visiting or not
for (int i = 0 ; i < size ; ++i)
{
if (visit[i] == -1)
{
result = 0 ;
break ;
}
}
}

cout<<("\n  ---------------") ;

if ( result == 1)
{
cout<< "\n This is a Bipartite Graph \n";

}
else
{
//There are many posiblity
//Two adjacent nodes are have same color
//or Not visiting all nodes by given source
cout<< "\n This is not a Bipartite Graph\n" ;
}
cout<< " ---------------\n" ;
//Tracing the result by node color
//That is optional
for (int i = 0 ;  i < size ;  ++i)
{
//0 and 1 are indicates color
//if -1  ,  so that means node are not visit
cout<<" Node ["<< i <<"] -> color : "<< visit[i] <<"\n" ;

}

}
int main()
{
//Create Object
Graph g=Graph(7);
//First set node keys
g.setData();

//Connected two node with Edges
//Connected two node with Edges
g.addEdge ( 0 , 1) ;
g.addEdge ( 1 , 4) ;
g.addEdge ( 1 , 5) ;
g.addEdge ( 2 , 4) ;
g.addEdge ( 2 , 6) ;
g.addEdge ( 3 , 5) ;

g.printGraph();
g.bipartite();
return 0;
}``````

#### Output

`````` Adjacency list of vertex 0 : 1
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 4 6
Adjacency list of vertex 3 : 5
Adjacency list of vertex 4 : 1 2
Adjacency list of vertex 5 : 1 3
Adjacency list of vertex 6 : 2
---------------
This is a Bipartite Graph
---------------
Node [0] -> color : 0
Node [1] -> color : 1
Node [2] -> color : 1
Node [3] -> color : 1
Node [4] -> color : 0
Node [5] -> color : 0
Node [6] -> color : 0
``````
``````//Java program
//Check whether a given graph is Bipartite or not
//Using DFS
public class MyGraph
{

static class AjlistNode
{
int id;//Vertices node key
AjlistNode next;
}
static class Vertices
{
int data;
AjlistNode next;
}

//number of Vertices
public int size,result;
Vertices node[];

MyGraph(int size)
{
//set value
this.size = size;
result = 1;
node = new Vertices[size];

}

//set initial node value
public void setData()
{
if(node == null)
{
System.out.println("\nEmpty Graph");
}else
{
for(int index = 0; index < size; index++)
{
// avoid java.lang.nullPointerException
node[index]=new Vertices();
node[index].next=null;
}
}
}
//connect two nodes
public void connect(int start,int end)
{
AjlistNode newEdge=new AjlistNode();
newEdge.id=end;//end node
newEdge.next=null;
if(node[start].next==null)
{
node[start].next=newEdge;
}else
{
AjlistNode temp=node[start].next;

while(temp.next!=null)
{
temp=temp.next;
}
temp.next=newEdge;
}
}
{
if(start < size && end < size && node != null)
{
connect(start,end);
if(start==end)
{
//self loop
return;
}
connect(end,start);
}else{
System.out.println("\nEmpty Graph");
}
}

public void printGraph()
{

if(size>0 && node!=null)
{
for(int index=0;index < size;index++)
{
System.out.print("\nAdjacency list of vertex "+index+" :");

AjlistNode temp=node[index].next;

while(temp!=null)
{
System.out.print("  "+node[temp.id].data);

temp=temp.next;
}
}
}
}
//Method which is check a given undirected graph is an Bipartite or not?
//same to DFS
public void  is_bipartite(int position,
int  []visit,
int color)
{
//Base case
if(result==0) return;

if(visit[position]!=-1)
{
if(visit[position]!=color)
{
result=0;
//when need more then two color
visit[position]=2;
}
return;

}else
{

visit[position]=color;

AjlistNode  temp=node[position].next;

while(temp!=null)
{
is_bipartite(temp.id,visit,(color==0)?1:0);
temp=temp.next;
}
}
}

public void  bipartite()
{
int []visit= new int[size];

for ( int i = 0 ;  i < size ;  ++i)
{
//set -1 because 0 and 1 will used to color
visit[i] = -1 ;
}

is_bipartite( 0 , visit , 0 ) ;

if (result == 1)
{
//Check each vertex are visiting or not
for (int i = 0 ; i < size ; ++i)
{
if (visit[i] == -1)
{
result = 0 ;
break ;
}
}
}

System.out.println("\n  ---------------") ;

if ( result == 1)
{
System.out.println( "\n This is a Bipartite Graph \n");

}
else
{
//There are many posiblity
//Two adjacent nodes are have same color
//or Not visiting all nodes by given source
System.out.println( "\n This is not a Bipartite Graph\n") ;
}
System.out.println( " ---------------\n") ;
//Tracing the result by node color
//That is optional
for (int i = 0 ;  i < size ;  ++i)
{
//0 and 1 are indicates color
//if -1  ,  so that means node are not visit
System.out.println(" Node ["+ i +"] . color : "+ visit[i] ) ;

}

}

public static void main(String[] args)
{
int totalNode=7;

MyGraph g=new MyGraph(totalNode);

g.setData();

//Connected two node with Edges
g.addEdge ( 0 , 1) ;
g.addEdge ( 1 , 4) ;
g.addEdge ( 1 , 5) ;
g.addEdge ( 2 , 4) ;
g.addEdge ( 2 , 6) ;
g.addEdge ( 3 , 5) ;

g.printGraph();
g.bipartite();

}
}``````

#### Output

``````Adjacency list of vertex 0 :  1
Adjacency list of vertex 1 :  0  4  5
Adjacency list of vertex 2 :  4  6
Adjacency list of vertex 3 :  5
Adjacency list of vertex 4 :  1  2
Adjacency list of vertex 5 :  1  3
Adjacency list of vertex 6 :  2
---------------

This is a Bipartite Graph

---------------

Node [0] . color : 0
Node [1] . color : 1
Node [2] . color : 1
Node [3] . color : 1
Node [4] . color : 0
Node [5] . color : 0
Node [6] . color : 0
``````
``````#Python program
#Check whether a given graph is Bipartite or not
#Using DFS
def __init__(self,data):
self.id=data
self.next=None

class Vertices:
def __init__(self,data):
self.data=data
self.next=None

class Graph:
"""Constructor for Graph"""
def __init__(self, size):
self.size=size
self.node=[]
self.result=0

def setData(self):
if(self.size>0 and self.node!=None):

index=0
while(index<self.size):

self.node.append(Vertices(index))

index+=1

#connect two node with  edge
def connect(self,start,end):

if(self.node[start].next==None):

self.node[start].next=new_edge
else:

temp=self.node[start].next

while(temp.next!=None):

temp=temp.next

temp.next=new_edge

#start,end is two nodes
if(self.size > start and self.size > start):

self.connect(start,end)

if(start==end):
return

self.connect(end,start)

else:
print("Invalid nodes")

def printGraph(self):

if(self.size>0 and self.node!=None):

index=0

while(index < self.size):

print("\nAdjacency list of vertex {0} : ".format(index),end=" ")

temp=self.node[index].next

while temp!=None:

print(" {0}".format(temp.id),end=" ")

temp=temp.next

index+=1

def check_color(self,color):
if(color==0):
return 1
else:
return 0
#Method which is check a given undirected graph is an Bipartite or not?
#same to DFS
def  is_bipartite(self,position,visit,color) :

#Base case
if(self.result==0):
return

if(visit[position] != -1) :

if(visit[position]!=color) :

self.result=0
#when need more then two color
visit[position]=2

return

else :

visit[position]=color

temp=self.node[position].next

while(temp != None) :

self.is_bipartite(temp.id,visit,self.check_color(color))

temp=temp.next

def bipartite(self) :

visit=[-1]*self.size;

i = 0
self.result=1
self.is_bipartite( 0 , visit , 0 )

if (self.result == 1) :

i=0
#Check each vertex are visiting or not
while ( i < self.size ) :

if (visit[i] == -1) :

self.result = 0

break

i+=1

print("\n   ---------------------")
if (self.result == 1) :

print( "\n This is a Bipartite Graph \n")
else :

#There are many posiblity
#Two adjacent nodes are have same color
#or Not visiting all nodes by given source
print( "\n This is not a Bipartite Graph\n")
print( " ---------------------------\n")
#Tracing the result by node color
#That is optional
i=0
while (i < self.size ) :

#0 and 1 are indicates color
#if -1  , so that means node are not visit
print(" Node [", i ,"] -> color : ", visit[i] )
i+=1

def main():
g=Graph(7)
g.setData()
#Connected two node with Edges
g.printGraph()
g.bipartite()

if __name__=="__main__":
main()``````

#### Output

``````Adjacency list of vertex 0 :   1
Adjacency list of vertex 1 :   0  4  5
Adjacency list of vertex 2 :   4  6
Adjacency list of vertex 3 :   5
Adjacency list of vertex 4 :   1  2
Adjacency list of vertex 5 :   1  3
Adjacency list of vertex 6 :   2
---------------------

This is a Bipartite Graph

Node [ 0 ] -> color :  0
Node [ 1 ] -> color :  1
Node [ 2 ] -> color :  1
Node [ 3 ] -> color :  1
Node [ 4 ] -> color :  0
Node [ 5 ] -> color :  0
Node [ 6 ] -> color :  0
``````
``````//C# program
//Check whether a given graph is Bipartite or not
//Using DFS
using System;
public class AjlistNode
{
public int id;//Vertices node key
public AjlistNode next;
}
public class Vertices
{
public int data;
public AjlistNode next;
}
public class MyGraph
{

//number of Vertices
public int size,result;
public Vertices []node;

MyGraph(int size)
{
//set value
this.size = size;
result = 1;
node = new Vertices[size];

}

//set initial node value
public void setData()
{
if(node == null)
{
Console.WriteLine("\nEmpty Graph");
}else
{
for(int index = 0; index < size; index++)
{
// avoid java.lang.nullPointerException
node[index]=new Vertices();
node[index].next=null;
}
}
}
//connect two nodes
public void connect(int start,int end)
{
AjlistNode newEdge=new AjlistNode();
newEdge.id=end;//end node
newEdge.next=null;
if(node[start].next==null)
{
node[start].next=newEdge;
}else
{
AjlistNode temp=node[start].next;

while(temp.next!=null)
{
temp=temp.next;
}
temp.next=newEdge;
}
}
{
if(start < size && end < size && node != null)
{
connect(start,end);
if(start==end)
{
//self loop
return;
}
connect(end,start);
}else{
Console.WriteLine("\nEmpty Graph");
}
}

public void printGraph()
{

if(size>0 && node!=null)
{
for(int index=0;index < size;index++)
{
Console.Write("\nAdjacency list of vertex "+index+" :");

AjlistNode temp=node[index].next;

while(temp!=null)
{
Console.Write("  "+node[temp.id].data);

temp=temp.next;
}
}
}
}
//Method which is check a given undirected graph is an Bipartite or not?
//same to DFS
public void  is_bipartite(int position,
int  []visit,
int color)
{
//Base case
if(result==0) return;

if(visit[position]!=-1)
{
if(visit[position]!=color)
{
result=0;
//when need more then two color
visit[position]=2;
}
return;

}else
{

visit[position]=color;

AjlistNode  temp=node[position].next;

while(temp!=null)
{
is_bipartite(temp.id,visit,(color==0)?1:0);
temp=temp.next;
}
}
}

public void  bipartite()
{
int []visit= new int[size];

for ( int i = 0 ;  i < size ;  ++i)
{
//set -1 because 0 and 1 will used to color
visit[i] = -1 ;
}

is_bipartite( 0 , visit , 0 ) ;

if (result == 1)
{
//Check each vertex are visiting or not
for (int i = 0 ; i < size ; ++i)
{
if (visit[i] == -1)
{
result = 0 ;
break ;
}
}
}

Console.WriteLine("\n  ---------------") ;

if ( result == 1)
{
Console.WriteLine( "\n This is a Bipartite Graph \n");

}
else
{
//There are many posiblity
//Two adjacent nodes are have same color
//or Not visiting all nodes by given source
Console.WriteLine( "\n This is not a Bipartite Graph\n") ;
}
Console.WriteLine( " ---------------\n") ;
//Tracing the result by node color
//That is optional
for (int i = 0 ;  i < size ;  ++i)
{
//0 and 1 are indicates color
//if -1  ,  so that means node are not visit
Console.WriteLine(" Node ["+ i +"] . color : "+ visit[i] ) ;

}

}

public static void Main(String[] args)
{
int totalNode=7;

MyGraph g=new MyGraph(totalNode);

g.setData();

//Connected two node with Edges
g.addEdge ( 0 , 1) ;
g.addEdge ( 1 , 4) ;
g.addEdge ( 1 , 5) ;
g.addEdge ( 2 , 4) ;
g.addEdge ( 2 , 6) ;
g.addEdge ( 3 , 5) ;

g.printGraph();
g.bipartite();

}
}``````

#### Output

``````Adjacency list of vertex 0 :  1
Adjacency list of vertex 1 :  0  4  5
Adjacency list of vertex 2 :  4  6
Adjacency list of vertex 3 :  5
Adjacency list of vertex 4 :  1  2
Adjacency list of vertex 5 :  1  3
Adjacency list of vertex 6 :  2
---------------

This is a Bipartite Graph

---------------

Node [0] . color : 0
Node [1] . color : 1
Node [2] . color : 1
Node [3] . color : 1
Node [4] . color : 0
Node [5] . color : 0
Node [6] . color : 0
``````
``````<?php
/*
* PHP Program
//Check whether a given graph is Bipartite or not
//Using DFS
*/

class AjlistNode
{
public \$vId;
public \$next;
function __construct(\$vId)
{
\$this->vId=\$vId;
\$this->next=NULL;
}
}
class Node
{
public \$data;
public \$next;
function __construct(\$data)
{
\$this->data=\$data;
\$this->next=NULL;

}
}
class MyGraph
{

public \$node;
public \$size;
function __construct(\$size)
{
\$this->size=\$size;
\$this->node=[];  //empty array
}
public function setData()
{
if(\$this->size>0)
{
for(\$index=0;\$index<\$this->size;\$index++)
{
\$this->node[\$index]=new Node(\$index);
}

}
}
public function connect(\$start,\$end)
{
\$newEdge=new AjlistNode(\$end);
if(\$this->node[\$start]->next==NULL)
{
\$this->node[\$start]->next=\$newEdge;
}
else
{

\$temp=\$this->node[\$start]->next;
while(\$temp->next!=NULL)
{
\$temp=\$temp->next;
}
\$temp->next= \$newEdge;
}
}
{
if(\$this->size > \$start && \$this->size>\$end)
{
\$this->connect(\$start,\$end);
if(\$start!=\$end)
{
\$this->connect(\$end,\$start);
}

}
else
{
echo "\n Invalid node";
}
}
public function printGraph()
{
if(\$this->size>0 && count(\$this->node)>0 && \$this->node!=NULL)
{
for(\$index=0;\$index<\$this->size;\$index++)
{
echo ("\nAdjacency list of vertex ".\$index." : ");
\$temp=\$this->node[\$index]->next;
while(\$temp!=NULL)
{
echo (" ".\$this->node[\$temp->vId]->data);
\$temp=\$temp->next;
}
}
}
}

//Method which is check a given undirected graph is an Bipartite or not?
//same to DFS
public function  is_bipartite(\$position,&\$visit,\$color,&\$result)
{
//Base case
if(\$result==0) return;

if(\$visit[\$position]!=-1)
{
if(\$visit[\$position]!=\$color)
{
\$result=0;
//when need more then two color
\$visit[\$position]=2;
}
return;

}else
{

\$visit[\$position]=\$color;

\$temp= \$this->node[\$position]->next;

while(\$temp!=NULL)
{
\$this->is_bipartite(\$temp->vId,\$visit,(\$color==1)?0:1,\$result);
\$temp=\$temp->next;
}
}
}

public function  bipartite()
{
\$visit=array_fill(0, \$this->size, -1);
\$result=1;

\$this->is_bipartite(0, \$visit,0,\$result);

if(\$result==1)
{
//Check each vertex are visiting or not
for (\$i=0; \$i<  \$this->size;++ \$i)
{
if ( \$visit[\$i]==-1)
{
\$result=0;
break ;
}
}
}

echo ("\n ---------------");

if ( \$result==1)
{
echo  "\n This is a Bipartite Graph\n";

}
else
{
//There are many posiblity
//Two adjacent nodes are have same color
//or Not visiting all nodes by given source
echo  "\n This is not a Bipartite Graph\n";
}
echo  "---------------\n";
//Tracing the result by node color
//That is optional
for (\$i=0;  \$i<  \$this->size; ++ \$i)
{
//0 and 1 are indicates color
//if -1  ,  so that means node are not visit
echo " Node[\$i]-> color : ". \$visit[\$i]."\n";

}

}
}

function main()
{
//create object
\$g=new MyGraph(7);
\$g->setData();

//Connected two node with Edges

//Connected two node with Edges
\$g->addEdge ( 0 , 1) ;
\$g->addEdge ( 1 , 4) ;
\$g->addEdge ( 1 , 5) ;
\$g->addEdge ( 2 , 4) ;
\$g->addEdge ( 2 , 6) ;
\$g->addEdge ( 3 , 5) ;

\$g->printGraph();
\$g->bipartite();

}
main();
?>``````

#### Output

``````Adjacency list of vertex 0 :  1
Adjacency list of vertex 1 :  0 4 5
Adjacency list of vertex 2 :  4 6
Adjacency list of vertex 3 :  5
Adjacency list of vertex 4 :  1 2
Adjacency list of vertex 5 :  1 3
Adjacency list of vertex 6 :  2
---------------
This is a Bipartite Graph
---------------
Node[0]-> color : 0
Node[1]-> color : 1
Node[2]-> color : 1
Node[3]-> color : 1
Node[4]-> color : 0
Node[5]-> color : 0
Node[6]-> color : 0
``````

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post