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.

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);
    }
}

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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