## DEV Community

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`.

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[][]){
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;
}
else if(color[it]==color[n]){
return false;
}
}
}
return true;
}
}
``````

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[][]){
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
}
else if(color[it]==color[n]){
return false;
}
}
}
return true;
}
}
``````

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