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

You're given an undirected graph as an adjacency list graph, where graph[i] lists the neighbors of node i. Decide whether the graph is bipartite — that is, whether its nodes can be split into two groups (colored with 2 colors) so that no edge ever joins two nodes from the same group.

Input Format
Implement isBipartite(graph). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
graph = [[1,3],[0,2],[1,3],[0,2]]
Output
true

Example 2

Input
graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output
false
Constraints
  • 1 <= V <= 200
  • 0 <= E <= V*(V-1)/2
Test Cases (2)
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.

javascript
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];
    let head = 0;
  while (head < q.length) {
      const u = q[head++];
      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