Bipartite check
A graph is bipartite when its nodes split into two sides with every edge crossing between them, like students and the clubs they join. Colour one node, give each neighbour the other colour, and keep spreading. Any edge between two nodes of the same colour proves no split exists.
queue: front on the left, side in each box
Can every node go on one of two sides so that each edge joins the two sides? Try to colour it with a breadth-first search.
1function isBipartite(adj) {2 const side = new Array(adj.length).fill(-1);3 for (let s = 0; s < adj.length; s++) {4 if (side[s] !== -1) continue;5 side[s] = 0;6 const queue = [s];7 while (queue.length > 0) {8 const u = queue.shift();9 for (const v of adj[u]) {10 if (side[v] === -1) {11 side[v] = 1 - side[u];12 queue.push(v);13 } else if (side[v] === side[u]) return false;14 }15 }16 }17 return true;18}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | V + E | a clash near the start ends the search early |
| average | V + E | every node and edge is looked at once |
| worst | V + E | a bipartite graph: everything gets coloured |
| space | V | a side per node, plus the queue |
Where it breaks
- Odd loops are the only obstacle. Pick Odd ring: going round five nodes, the colours alternate and the fifth ends up next to the first with the same colour. A graph is bipartite exactly when it has no loop of odd length.
- Every part needs a start. Pick Two parts: the second part, D, E and F, is never reached from A. The outer loop starts a new search there, and finds the triangle that makes it fail.
- Why it matters. Matching problems, such as assigning workers to jobs or students to projects, are only solved efficiently on bipartite graphs. This check is often the first step.