Bipartite Check
Two-colour the graph with BFS; an edge between two vertices of the same colour means an odd cycle.
Decision · step 3 of 15DFS Checks: Two-colouring an even cycle
From 0 (colour 0), 1 is uncoloured: give it 1 and queue it.
What you will see
Alternating colours (and shapes) spread by layers; a conflicting edge flashes.
Cost
| Best | O(V + E) |
|---|---|
| Average | O(V + E) |
| Worst | O(V + E) |
| Space | O(V) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, try operations in any order.
Screen readers: Vertices announce name, neighbours and state (in queue, visited, current); each step announces which vertex is processed and which neighbours are discovered.
Reduced motion: Frontier and visited changes are crossfades; the traversal edge is emphasized without a travelling token.