Is Graph Bipartite?
Decide whether an undirected graph's nodes split into two sides with every edge crossing between them, by coloring each component with BFS.
Problem Understanding
Is Graph Bipartite?: given an undirected graph of n nodes as an adjacency list graph, return true if its nodes can be split into two sets A and B so that every edge joins a node in A to a node in B.
Examples: [[1,2,3],[0,2],[0,1,3],[0,2]] → false (0, 1, 2 form a triangle); [[1,3],[0,2],[1,3],[0,2]] → true ({0, 2} and {1, 3}).
The Intuition: Paint Neighbors the Opposite Color
Pick any node and put it on side A. Every neighbor must then be on side B, every neighbor of those on A, and so on: the sides are forced. That is a breadth-first search that paints instead of measuring distance.
- Uncolored neighbor: paint it the opposite color and queue it.
- Neighbor on the other side: fine, the edge crosses.
- Neighbor on the same side: contradiction, return false.
- Disconnected graph: restart from any uncolored node.
A graph is bipartite exactly when it has no odd-length cycle. See the bipartite graph visualizer for the same idea drawn as two columns, and Course Schedule for another BFS over every node of a graph.
Interactive Walkthrough
GREEN = SIDE A · DARK = SIDE B · RED = SAME-SIDE EDGE
ALL UNCOLOURED
u
:
neighbour
:
answer
:
queue
4 nodes, all uncoloured. Every edge must join side A to side B
Next
Node 0 is uncoloured: put it on side A and start a BFS from it
edges
Green nodes are side A, dark nodes side B. The edge being checked is solid; edges a node was painted across stay green. Try Two parts to see the search restart in a second component.
Dry Run Table
Input: LeetCode example 1, edges 0-1, 0-2, 0-3, 1-2, 2-3.
| Step | Node | What happens | Queue |
|---|---|---|---|
| start | 0 | color 0 = A | [0] |
| pop | 0 | paint 1, 2, 3 as B | [1, 2, 3] |
| pop | 1 | 0 is A: fine | [2, 3] |
| check | 1 | 2 is B, same as 1 |
Answer: false. The edge 1-2 has both ends on side B, closing the odd cycle 0-1-2.
The Solution Template
One BFS per uncolored node; color doubles as the visited array.
Is Graph Bipartite? Code
1var isBipartite = function(graph) {2 const color = new Array(graph.length).fill(-1);3 for (let s = 0; s < graph.length; s++) {4 if (color[s] !== -1) continue;5 color[s] = 0;6 const queue = [s];7 for (let head = 0; head < queue.length; head++) {8 const u = queue[head];9 for (const v of graph[u]) {10 if (color[v] === -1) {11 color[v] = 1 - color[u];12 queue.push(v);13 } else if (color[v] === color[u]) {14 return false;15 }16 }17 }18 }19 return true;20};
Edge Cases & Common Mistakes
- Disconnected graph: one BFS from node 0 misses other components; loop over all nodes.
- Isolated nodes: a node with no edges is trivially fine; it just gets side A.
- Using a separate visited set:
color[v] == -1already means unvisited. - Even vs odd cycles: a square is bipartite, a triangle or pentagon is not.
- Coloring on pop instead of on push: color when queueing, or a node can be queued twice with conflicting colors.
Summary
BFS from every uncolored node, giving neighbors the opposite color; a neighbor with the same color means an odd cycle, so return false. O(V + E) time, O(V) space.
More practice: DSA interview questions with answers · patterns cheat sheet