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)