Check if a graph is Bipartite or not Leetcode
Published: 2022-07-24 02:32:00

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/kc0pgjqbmtz8amorf851.jpg)

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_

```java
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;
    }
}
```

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

```java
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;
    }
}
```

**Solution**: Using `Depth-First Search`

```java
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;
    }
}
```