Be the first user to complete this post

Add to List 
Check if Graph is Bipartite  Adjacency List using BreadthFirst Search(BFS)
Objective: Given a graph represented by the adjacency List, write a BreadthFirst Search(BFS) algorithm to check whether the graph is bipartite or not.
Earlier we have solved the same problem using DepthFirst Search (DFS). In this article, we will solve it using BreadthFirst Search(BFS). Before we proceed, if you are new to Bipartite graphs, lets brief about it first
Bipartite Graphs OR Bigraphs is a graph whose vertices can be divided into two independent groups or sets so that for every edge in the graph, each end of the edge belongs to a separate group. There should not be any edge where both ends belong to the same set. Please read "Introduction to Bipartite Graphs OR Bigraphs".
Example:
Please read the following recommended articles before continue
Approach: Coloring of vertices  Check if Graph TwoColorable using BFS
Choose three colors RED, GREEN, WHITE. As you know in Bipartite graph, both ends of each edge belong to separate group, Let's say here two groups are RED and GREEN and for a graph to be bipartite, for each edge one end has to be RED and another end has to be GREEN.
 Initially color all the vertices in WHITE and as algorithm advances, these vertices will be colored as RED or GREEN.
 Initialize queue.
 Pick a vertex with color WHITE, now color it with RED. Add it to the queue.
 While the queue is not empty
 take out a vertex from the queue. let's say its vertex v.
 Now check all the neighbors of vertex v.
 If these neighbors are in WHITE color, color them with the alternate color of vertex v means if v is RED, color the neighbors in GREEN and if v is GREEN, color the neighbors in RED. and add these neighbors in the queue.
 If any of these neighbors are not in WHITE color, which means it was already colored earlier, check its color and if it has the same color as vertex v that means vertices connecting v and this neighbor cannot be in two colors means the graph is not bipartite. return false.
 Do steps 3 and 4 until all the vertices are in either RED or GREEN color if that happens means graph is bipartite.
Time Complexity O(V+E)
Code:
Output:
Graph is Bipartite: false  Graph is Bipartite: true
Also Read: