Graph is Bipartite or not?

A Bipartite Graph is a graph whose vertices can be divided into two independent sets, U and V such that every edge (u, v) either connects a vertex from U to V or a vertex from V to U. In other words, for every edge (u, v), either u belongs to U and v to V, or u belongs to V and v to U. We can also say that there is no edge that connects vertices of same set.

A bipartite graph is possible if the graph coloring is possible using two colors such that vertices in a set are colored with the same color. Note that it is possible to color a cycle graph with even cycle using two colors.

We can solve this problem using Breadth First Search (BFS).

Discussion :

public static boolean isBipartiteUtil(int G[][], int src, int colorArr[]) { 
 colorArr[src] = 1; 
 LinkedList<Integer> q = new LinkedList<Integer>(); 
 q.add(src); 
 while (!q.isEmpty()) { 
  int u = q.poll(); 
  if (G[u][u] == 1) return false; 
  for (int v = 0; v < V; ++v) { 
   if (G[u][v] ==1 && colorArr[v] == -1) { 
    colorArr[v] = 1 - colorArr[u]; 
    q.push(v); 
   } else if (G[u][v] ==1 && colorArr[v] == colorArr[u]) return false; 
  } 
 } 
 return true; 
} 

public static boolean isBipartite(int G[][]) { 
 int colorArr[] = new int[V]; 
 for (int i = 0; i < V; ++i) { colorArr[i] = -1; }
 for (int i = 0; i < V; i++) {
  if (colorArr[i] == -1) {
   if (isBipartiteUtil(G, i, colorArr) == false) return false; 
  }
 }
 return true; 
}

Time Complexity of the above approach is same as that Breadth First Search. In above implementation is O(V^2) where V is number of vertices. If graph is represented using adjacency list, then the complexity becomes O(V+E).