A Bipartite Graph is a graph whose vertices can be divided into two independent sets, U and V such that every edge (u, v) either connects a vertex from U to V or a vertex from V to U. In other words, for every edge (u, v), either u belongs to U and v to V, or u belongs to V and v to U. We can also say that there is no edge that connects vertices of same set.

A bipartite graph is possible if the graph coloring is possible using two colors such that vertices in a set are colored with the same color.

Below code implements this algorithm.

**Java**

*Time complexity: O(V+E)*

Space complexity: O(V)

public class BipartiteGraphValidator {
public static <V> boolean isBipartite(Graph<V> g){
if (g == null || g.V() <= 1){
return false;
}
Map<V, Boolean> coloredPath = new HashMap<>();//strongly connected graphs only
Queue<V> q = new LinkedList<V>();
V source = g.getVertexes().iterator().next();
q.offer(source);
coloredPath.put(source, Boolean.TRUE);
while (q.size() > 0){
V curr = q.poll();
for (V neighb : g.adj(curr)){
if (coloredPath.containsKey(neighb) && color(curr, coloredPath) == color(neighb, coloredPath)){
return false;
}
if (!coloredPath.containsKey(neighb)){
q.offer(neighb);
}
coloredPath.put(neighb, !color(curr, coloredPath));
}
}
return true;
}
private static <V> boolean color(V v, Map<V, Boolean> coloredPath){
return coloredPath.get(v);
}
}

### Like this:

Like Loading...