Skip to main content

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.

bipartite graph example

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)
{

  // create Adjacency node
  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
    {
      //Add node at last
      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);
  }
}
//Display Adjacency list of vertex
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
    addEdge(node,0, 1); 
    addEdge(node,1, 4); 
    addEdge(node,1, 5);
    addEdge(node,2, 4); 
    addEdge(node,2, 6); 
    addEdge(node,3, 5);

    //addEdge(node,3, 1);
    
    //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 addEdge(int,int);
  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
    //first create Adjacency node
  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
    {
            //Add node at last
      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;
  }
}

//Display Adjacency list of vertex
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].data=index;//set your data
                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;
        }
    }
    //Add edge at the end
    public void addEdge(int start,int end)
    {
        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
class AjLinkeNode:
  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):

    new_edge=AjLinkeNode(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  

  #add edge
  def addEdge(self,start,end):
     
    #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.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()

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].data=index;//set your data
        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;
    }
  }
  //Add edge at the end
  public void addEdge(int start,int end)
  {
    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;
    }
  }
  public function addEdge($start,$end)
  {
    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
Last updated on by Kalkicode




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.

New Comment