The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+3 votes
Is DFS can be applied to check that a graph is bipartite or not?
asked in DS by Boss (6.6k points) | 251 views
Why...we want to check only that graph is bipartite or not...
every time color the child different from parent.
i m nt getting u plzz explain more.
We have to use only 2 colors to check..So every time child is having different color from parent..
I dnt know...may be there is any exception.

1 Answer

+8 votes
Best answer

Yes. It can be done in the following way,

Explanation :

  • Above is a bipartite graph
  • If we crawl through the graph using dfs , one step at a time and verify the nodes for different colors, then we will find that this graph is indeed bipartite.
  • So, obviously why not crawl through an uncolored graph and color it one - by- one node and flipping the color every alternatively. we can definitely do it , if the graph is indeed bipartite. 



// set bipartite flag as true initially
bool flag = true;
void dfs(int u,int color){  
    // if unvisited node
    if(!visited[u]) {
        visited[u] = true; // mark as visited
        node_color[u] = color; // color this node u with color
        // checking all nodes in the row of u in the matrix
        for ( all v :: an adjacent vertices of u)  {
           // do the following
           if ( there is an edge between u and v){ // edge between v and u
               // if color of vertex v is equal to color of u,
               // then we are not able to color any further
               if (color of v:adjacent == my_color(u) ) { 
                     // graph is not bipartite so return
                     set bipartite flag as zero (false)
                     return from this dfs;             
               // flip the color and continue dfs
               if (adjacent: v is not visited) {
                 // recurse dfs again

How will it detect odd length cycle?

In the following way,

Actual Implementation:

// graph represented using adjacentcy matrix
#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;
bool b_flag = true;
// V = max_nodes
int V;
//  color can be 0 or 1
// main dfs function
void dfs(int u,int color,std::vector<std::vector<bool>> adj,int visited[],int node_color[]){  
    if(!visited[u] && b_flag) {
        visited[u] = true;
        node_color[u] = color; // color this node u with color
        // checking all nodes in the row of u in the matrix
        for (int v = 0; v < V; v++)  {
           if ( adj[u][v] == 1){ // edge between v and u
               // if color of vertex v is equal to color of u,
               // then we are not able to color any further
               if (node_color[v] == color) { 
                     // graph is not bipartite so return
                     b_flag = false; 
               // flip the color and continue dfs
               if (!visited[v]) {
                 dfs(v,(color == 1)?0:1,adj,visited,node_color); 
int main(int argc, char const *argv[]) { 
  // enter you no of vertices 
  // declare required variables and arrays
  // adjacency matrix use for graph representation
  // node_color[V] will store the color 
  // of every vextices while coloring 
  // vector are used for random access
  // and to avoid all those pointer casting problems
  std::vector<std::vector<bool>> adj(V, std::vector<bool>(V));
  int node_color[V];
  for(int m = 0;m<V;m++) node_color[m] = -1; // initial node colors -1 = uncolored
  int visited[V] = {0}; // all are unvisited nodes now
  // initialize the matrix
  for(int i=0;i<V;i++) {
    for(int j=0;j<V;j++) {
      adj[i][j] = 0;
  // matric initialization done !
  // scan through the input file
  // and develop the adjacency matrix
  // node numbers are starting from index 0 to V-1
  int u,v;
  while(scanf("%d %d",&u,&v) != EOF) {
    // read one line of input
    // read two nodes
    //scanf("%d %d",&u,&v);
    // u and v have a bidirectional edge between them
    adj[u][v] = adj[v][u] = 1;   
  // use a color variable
  // actually boolean type can be used
  // for color
  int color; 
  // call dfs() now
  // using for loop here to handle disconnected graph as well
  // after completing one dfs tree 
  // we must need to jump
  // to another tree
  int node = 0;
  for(int node=0;node<V;node++) {
    color = 1;
    // count ++;
    // We can use this counter to count 
    // the the no of connected componentes..//
    // For connected graph this dfs call
    // will invoke only once from here .. //
    // For disconnected graph 
    // dfs will be invoked count times 
    // from this for loop
    // ...............................
  // checking the flag now
  if(b_flag) {
    printf("G is bipartite\n");
  }else {
    printf("G is not bipartite\n");
  return 0;

compile: g++ -std=c++11 bipartite.cpp

input file: 

  • First line contains No of vertices
  • Remaining lines should contain vertices pairs representing one bi-directional edge
  • Vertex indices starts from 0 to V-1
// input.txt

0 1
0 2
1 3
3 2
4 5
6 4
5 6

Execute :a.exe < input.txt

O/P : G is not bipartite


answered by Veteran (57.5k points)
selected by
i m not able to run this code online.... i u have then plzz tell me the link ?
Dear Coder, I guess GATE will give options with reasons.

Is coding coming in GATE 2017 ?  :P :D :)
But where that condition @Debasish to see it is not joining like regular graph

means where we could see that it must have 2 partition in graph?
same logic with bfs !

only different way of the traverse.
ok for dfs.

but where bipartite portion?
you need two partitions right ?

Just traverse one more time, after successful coloring has been done.

  • Whenever you arrive at node with color == WHITE/BLACK ...raise some flag ( hey! found one white/black node !!! ) or put that vertex somewhere (use different data structure).
  • Or, you can collect the partitions while coloring,( only thing more code !)

I think it is..... although it is new for me :)
see last problem on this link.

explanation added !

@saurabh rai 

Now you will be able to run this code. Updated ! Just be careful with the input file


argc, argv u took to counting number of vertices ,rt?

then where u r taking input for vertices?

And what <vector> header file is doing?

Actually it is causing problem somehow
argc, use here.

Input is taken from input file while running ( i have shown the command)

Vector is just a collection ( datastructure) used to build the matrix. Conceptually Same as 2D matrix in this program.
You can edit the node pairs in the input file ( take siple graph only , not multiple edge graph)

And execute in above manner.

It should show yes/no.. depending on your selected graph.

Both input file + cpp file shld reside in same folder.
very nice @debashish

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,100 questions
36,904 answers
34,770 users