recategorized by
1,382 views
3 votes
3 votes
Is DFS can be applied to check that a graph is bipartite or not?
recategorized by

1 Answer

Best answer
8 votes
8 votes

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

selected by

Related questions

0 votes
0 votes
2 answers
1
0 votes
0 votes
2 answers
2
yuuchan asked Jul 22, 2023
475 views
If G is a complete bipartite graph with n vertices (n >= 2) and minimum number of edges, then matching number of G is ____1n-1⌊n/2⌋⌈n/2⌉
0 votes
0 votes
1 answer
4
Lakshman Bhaiya asked Oct 10, 2018
1,177 views
The number of ways to properly color (using just sufficient colors) a connected graph without any cycle using five colors, such a way that no two adjacent nodes have the ...