8.5 Bipartite Check / Graph Coloring

Demo: Is Graph Bipartite? — LC 785 (Medium — Meta/Google High)

Statement (Demo): Given an undirected graph, return whether it is bipartite — its nodes can be split into two groups so every edge joins the two groups. Example: graph=[[1,3],[0,2],[1,3],[0,2]] → true | ⚡ nodes ≤ 100

Approach: From each uncolored node, BFS and give neighbours the alternate color (1/-1). If an edge connects two nodes of the same color, the graph is not bipartite. Loop over every node to cover disconnected components.

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

Complexity: Time O(V + E), Space O(V)