Bipartite Graph

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

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

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

While doing BFS traversal, each node in the BFS tree is given the opposite color to its parent. If there exists an edge connecting current vertex to a previously-colored vertex with the same color, then we can safely conclude that the graph is not bipartite.
 

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

If a graph contains an odd cycle, we cannot divide the graph such that every adjacent vertex has different color. To check if a given graph is contains odd-cycle or not, we do a breadth-first search starting from an arbitrary vertex v. If in the BFS, we find an edge, both of whose end-points are in the same level, then the graph is not Bipartite and odd-cycle is found. Here, level of a vertex is its minimum distance from the starting vertex v. So, odd-level vertices will form one set and even-level vertices will form another.

  odd-cycle-bfs

Please note that if the graph has many connected components and each component bipartite, them the graph is bipartite graph. Below code assume that given graph is connected and checks if the graph contains an odd cycle or not.

 
C++ implementation –
 

Download   Run Code

Output:

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
Sort by:   newest | oldest | most voted
Vaishali Goyal
Guest
Vaishali Goyal

Will it work for directed graph, that is not strongly connected but connected?

Abhishek
Guest
Abhishek

Line no. 22 throws a compilation error !

There should be == instead of = in line 78

wpDiscuz