Determine if a given graph is Bipartite Graph using DFS

Given a graph, check if given graph is bipartite graph or not. A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V.


 
Below graph is a Bipartite Graph as we can divide it into two sets U and V with every edge having one end point in set U and the other in set V

  bipartite-graph-svg

 
It is possible to test whether a graph is bipartite or not using Depth-first search algorithm. There are two ways to check for Bipartite graphs –

1. A graph is bipartite if and only if it is 2-colorable.

2. A graph is bipartite if and only if it does not contain an odd cycle.

In previous post, we have checked if the graph contains an odd cycle or not using BFS. Now using DFS, we will check if the graph is 2-colorable or not.

The main idea is to assign to each vertex the color that differs from the color of its parent in the depth-first search tree, assigning colors in a preorder traversal of the depth-first-search tree. If there exists an edge connecting current vertex to a previously-colored vertex with the same color, then we can say that the graph is not bipartite.

 
C++ implementation –
 

Download   Run Code

Output:

Not a Biparte Graph

 
The time complexity of above solution is O(n + m) where n is number of vertices and e is number of edges in the graph. Please note that O(m) may vary between O(1) and O(n2), depending on how dense the graph is.

References: https://en.wikipedia.org/wiki/Bipartite_graph

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz