Check whether a given graph is Bipartite or not Medium 0 attempts
GeeksforGeeks ↗

Check whether a given graph is Bipartite or not

Medium GraphBFSDFS GeeksforGeeks

Given a graph, determine whether it is bipartite — can nodes be colored with 2 colors such that no two adjacent nodes share a color?

Example: graph = [[1,3],[0,2],[1,3],[0,2]] → Output: true

Sample Input
—
Sample Output
—
Constraints
  • 1 <= V <= 200
  • 0 <= E <= V*(V-1)/2
Test Cases
Case 1
Args: [[[1,3],[0,2],[1,3],[0,2]]] Expected: true
Case 2
Args: [[[1,2,3],[0,2],[0,1,3],[0,2]]] Expected: false
Topics
GraphBFSDFS

BFS Coloring

Try 2-coloring the graph with BFS. If any conflict is found, it's not bipartite.

function isBipartite(graph) {
  const n = graph.length, color = Array(n).fill(-1);
  for (let i = 0; i < n; i++) {
    if (color[i] !== -1) continue;
    color[i] = 0;
    const q = [i];
    while (q.length) {
      const u = q.shift();
      for (const v of graph[u]) {
        if (color[v] === -1) { color[v] = 1 - color[u]; q.push(v); }
        else if (color[v] === color[u]) return false;
      }
    }
  }
  return true;
}

Time: O(V + E) | Space: O(V)

Saved in this browser only. Private to you.

JavaScript