How to check a graph is bipartite graph or not?
As bansal said, its abailable there. Read the text and then check videoes if any. DO NOT SKIP VIDEOES, they make algo crystal clear!!
If doubt still persists, get back to us 
Bipartite Graphs are those, whose vertices can be divided into two independent sets.
Say that you have two colors Red and Blue. If it is possible to color the graph in such a way, that all nodes connected to a Red colored node directly by an edge are colored Blue, and vice versa then the graph is Bipartite. Else it’s not.
The above example allows us to formulate a nice algorithm to check whether a given graph is Bipartite or not. We will traverse the graph using Breadth First Search.
- Start with an arbitary node. Color it Red.
- Look at all neighbors of the current node. If it is colored Red, and the neighboring nodes are not colored, color them Blue and push it in the Queue to check that node later. If the neighboring node is already colored Blue, ignore. If the neighboring node is colored Red, then the graph cannot be Bipartite and exit the traversal.
- Note that even if the traversal is completed after starting from the arbitarily chosen node, we cannot guarantee Bipartiteness unless we have checked all the nodes. It may so happen that there are multiple independent sub-graphs (by sub-graphs I mean different graphs made by the set of nodes given such that they don’t have any edge in between them). In that case choose an arbitary node which is not colored, and go back to step 1.
Reference - Check whether a given graph is Bipartite or not - GeeksforGeeks (already stated by @bansal1232)
A good problem to try out the above logic can be - CHFNFRN Problem - CodeChef
This problem is a direct application of the above algorithm. So it will provide a good hands-on learning!
I feel this answer is self-sufficient, but should you face any problem, do comment.
2 Likes