251 views
Is DFS can be applied to check that a graph is bipartite or not?
asked in DS | 251 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.

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]) {
}
}
}
}
}
//.............................................................................................
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

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++) {
}
}
// 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
//scanf("%d %d",&u,&v);
// u and v have a bidirectional edge between them
}
//......................................
// 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;
// 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
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.

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

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