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[][]){
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**

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

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

## Top comments (0)