Check If Graph is Bipartite

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.

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();
        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)){
                coloredPath.put(neighb, !color(curr, coloredPath));

        return true;

    private static <V> boolean color(V v, Map<V, Boolean> coloredPath){
        return coloredPath.get(v);


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s