DEV Community

Prashant Mishra
Prashant Mishra

Posted on • Originally published at leetcode.com

Check if a graph is Bipartite or not Leetcode

In simpler terms a graph is called Bipartite graph if no two nodes in the graph have the same color where number of colors allowed are only two.

bipartiteImage

The above graph can be called as Bipartite graph,
Explanation:
Let two color allowed are red and blue.
If we color node 0 with color red then its adjacent node 1 can be colored with blue and 3 can be colored with blue.
Since both node 3 and 1 have their adjacent nodes as 2 and 2 can be colored with red color .
Hence no two adjacent nodes have the same color.
Hence above graph is called as Bipartite graph.

Note: Its possible to color graph with two colors if it has even-node cycle (i.e. even no. of nodes forming cycle) but its not possible for odd-cycle graph(when odd no. of nodes form cycle).

Solution: Using simple Breadth-first Algorithm

Remember we are using 0 and 1 as two different colors

class Solution {
    public boolean isBipartite(int[][] graph) {
        int visited[] = new int[graph.length];
        int color[] = new int[graph.length];
        for(int i =0;i<graph.length;i++){
// using for loop for all components of the graph.
            if(visited[i]==0){
                visited[i] =1;
                color[i] =0;
                if(!isPossible(i,visited,color,graph)) return false;
            }
        }
        return true;

    }
    public boolean isPossible(int node, int[] visited, int color[], int graph[][]){
        Queue<Integer> q = new LinkedList<>();
        q.add(node);
        while(!q.isEmpty()){
            Integer n = q.remove();
            for(int it: graph[n]){
                if(visited[it]==0){
                    visited[it] = 1;
                    if(color[n]==0) color[it] = 1;
                    else color[it] =0;
                    q.add(it);
                }
                else if(color[it]==color[n]){
                     return false;
                }
            }
        }
        return true;
    }
}
Enter fullscreen mode Exit fullscreen mode

We can remove visited Array , and reduce the lines of code as below

class Solution {
    public boolean isBipartite(int[][] graph) {
        int color[] = new int[graph.length];
        Arrays.fill(color,-1);
        for(int i =0;i<graph.length;i++){
            if(color[i]==-1){// color ==-1 means that i has not been visited
                color[i] =0;// initially color it with 0
                if(!isPossible(i,color,graph)) return false;
            }
        }
        return true;
    }
    public boolean isPossible(int node,int color[], int graph[][]){
        Queue<Integer> q = new LinkedList<>();
        q.add(node);
        while(!q.isEmpty()){
            Integer n = q.remove();
            for(int it: graph[n]){
                if(color[it] ==-1){
                    color[it] = 1-color[n]; // so if n's color was 0 , `it` color will be 1 , else 0
                    q.add(it);
                }
                else if(color[it]==color[n]){
                     return false;
                }
            }
        }
        return true;
    }
}
Enter fullscreen mode Exit fullscreen mode

Solution: Using Depth-First Search

class Solution {
    // using depth first search for checking bipartite graph
    public boolean isBipartite(int[][] graph) {

        int color[] = new int[graph.length];
        Arrays.fill(color,-1);
        for(int i =0;i<graph.length;i++){
            if(color[i]==-1){
                color[i] = 1;
                if(!isPossible(i,color,graph)) return false;
            }
        }
        return true;
    }
    public boolean isPossible(int n, int[] color,int[][] graph){
        for(int node : graph[n]){
            if(color[node]==-1){
                color[node] = 1-color[n];
                if(!isPossible(node,color,graph)) return false;
            }
            else if (color[node] ==color[n]) return false;
        }
        return true;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)