@@ -0,0 +1,1369 @@
+package dtprogrammer.github.io.other.graph;%0A%0Aimport java.util.Arrays;%0Aimport java.util.LinkedList;%0Aimport java.util.Queue;%0A%0A/**%0A * Checks if the given graph is Bipartite%0A * http://www.geeksforgeeks.org/bipartite-graph/%0A */%0Apublic class Bipartite %7B%0A    boolean isBipartite(int G%5B%5D%5B%5D, int V) %7B%0A        int%5B%5D color = new int%5BV%5D;%0A%0A        // -1 represent uncolored i.e. unvisited too%0A        Arrays.fill(color, -1);%0A%0A        for (int i = 0; i %3C V; i++) %7B%0A            if (color%5Bi%5D == -1) %7B%0A                if (!isBipartite(G, V, i, color)) %7B%0A                    return false;%0A                %7D%0A            %7D%0A        %7D%0A        return true;%0A    %7D%0A%0A    private boolean isBipartite(int%5B%5D%5B%5D G, int V, int src, int%5B%5D color) %7B%0A%0A        // visit the source%0A        color%5Bsrc%5D = 1;%0A%0A        Queue%3CInteger%3E queue = new LinkedList%3C%3E();%0A%0A        queue.add(src);%0A%0A        while (!queue.isEmpty()) %7B%0A            Integer curNode = queue.poll();%0A%0A            for (int i = 0; i %3C V; i++) %7B%0A                // if there is an edge and the other node is unvisited%0A                if (G%5BcurNode%5D%5Bi%5D == 1 && color%5Bi%5D == -1) %7B%0A                    queue.add(i);%0A                    color%5Bi%5D = 1 - color%5BcurNode%5D;%0A                %7D else if (G%5BcurNode%5D%5Bi%5D == 1 && color%5Bi%5D == color%5BcurNode%5D) %7B%0A                    return false;%0A                %7D%0A            %7D%0A%0A        %7D%0A        return true;%0A    %7D%0A%7D%0A

Check whether a given graph is Bipartite