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)