GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
229 views
Is DFS can be applied to check that a graph is bipartite or not?
asked in DS by Boss (6.1k points)   | 229 views
yes...
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

+7 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. 

Logic:

 

// 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
                 dfs(v,opposite_color); 
               }
           }
         }
    }
}

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; 
                     return;             
               }
               // 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 
  scanf("%d",&V);
  // 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
  //printf("Hi3\n");
  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;
    dfs(node,color,adj,visited,node_color);
    // 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
  }
  //printf("Hi4\n");
    // ...............................
  // 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

7
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 (50.5k points)  
selected by
ok....
@Debasish

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,argv...no 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


Top Users Jul 2017
  1. Bikram

    4894 Points

  2. manu00x

    2888 Points

  3. Debashish Deka

    1870 Points

  4. joshi_nitish

    1776 Points

  5. Arjun

    1496 Points

  6. Hemant Parihar

    1306 Points

  7. Shubhanshu

    1128 Points

  8. Arnab Bhadra

    1114 Points

  9. pawan kumarln

    1114 Points

  10. Ahwan

    940 Points


24,089 questions
31,062 answers
70,677 comments
29,400 users