Bipartite Graph

Check whether a given graph is Bipartite or not. 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.

http://www.geeksforgeeks.org/bipartite-graph/

Solution 1: BFS + dye

    final static int V = 4; // # of Vertices

    public boolean isBipartite(int G[][], int src) {
        //  The value 1 is used to indicate first color is assigned and value 0 indicates second color is assigned.
        int colorArr[] = new int[V];
        Arrays.fill(colorArr, -1);
        colorArr[src] = 1;
        Queue<Integer> q = new LinkedList<>();
        q.add(src);
        while (!q.isEmpty()) {
            int u = q.poll();
            // Find all non-colored adjacent vertices
            for (int v = 0; v < V; ++v) 
                if (G[u][v] == 1 && colorArr[v] == -1) {
                    colorArr[v] = 1 - colorArr[u];
                    q.add(v);
                } else if (G[u][v] == 1 && colorArr[v] == colorArr[u])    return false;
        }
        return true;
    }