Is Graph Bipartite?

Examples

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

This graph is a simple cycle 0-1-2-3-0. Put nodes 0 and 2 in group A, and nodes 1 and 3 in group B - every edge connects an A to a B.

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false

Nodes 0, 1, and 2 are all directly connected to each other (a triangle). In any two-group split, at least two of those three nodes must land in the same group, which breaks the rule.

Input: graph = [[],[]]
Output: true

No edges at all means the rule is never violated, no matter how you split the nodes.

Constraints

• 1 <= graph.length <= 100

• The graph has no self-loops and no repeated edges.

Approach

This is a traversal problem in disguise as a coloring problem. Walk the graph (DFS or BFS both work), assigning each node one of two colors as you first reach it. The rule is simple: every neighbor of a node must get the opposite color from that node.

Whenever you're about to visit a neighbor, check first: if it's unvisited, color it the opposite of the current node and keep traversing from it. If it's already been colored, it had better be the opposite color of the current node - if it's the same color, two directly connected nodes ended up in the same group, which means the graph can't be split this way, so the answer is false.

Since the graph can be disconnected, make sure to restart the coloring from every node that hasn't been visited yet - each disconnected piece has to pass the same check independently.

Solutions

DFS - Two-Coloring

Color each node 1 or -1 as it's first visited. Recurse into every neighbor: if a neighbor is already the same color as the current node, the graph isn't bipartite; if it's uncolored, color it the opposite and keep going. Restart from any node not yet colored, to cover disconnected pieces.

function isBipartite(graph) {
  const n = graph.length;
  const color = new Array(n).fill(0); // 0 = uncolored, otherwise 1 or -1

  function dfs(node, c) {
    color[node] = c;

    for (const neighbor of graph[node]) {
      if (color[neighbor] === c) {
        return false;
      }
      if (color[neighbor] === 0 && !dfs(neighbor, -c)) {
        return false;
      }
    }

    return true;
  }

  for (let i = 0; i < n; i++) {
    if (color[i] === 0 && !dfs(i, 1)) {
      return false;
    }
  }

  return true;
}

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

BFS - Two-Coloring

Same coloring rule, but processed layer by layer with a queue instead of recursion: color a starting node, then repeatedly pop a node and check/color its neighbors.

function isBipartite(graph) {
  const n = graph.length;
  const color = new Array(n).fill(0);

  for (let i = 0; i < n; i++) {
    if (color[i] !== 0) continue;

    color[i] = 1;
    const queue = [i];

    while (queue.length > 0) {
      const node = queue.shift();

      for (const neighbor of graph[node]) {
        if (color[neighbor] === color[node]) {
          return false;
        }
        if (color[neighbor] === 0) {
          color[neighbor] = -color[node];
          queue.push(neighbor);
        }
      }
    }
  }

  return true;
}

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