DFS Checks
A depth-first search is a stack of calls, one per vertex, and the current path is that stack. Once you see it that way, several questions about a graph answer themselves during the search. A cycle in an undirected graph is an edge that reaches a vertex already visited, other than the one you just came from. In a directed graph the visited vertex must still be open on the path, since a finished vertex cannot lead back. Bipartiteness is the same idea with colours: give every neighbour the opposite colour, and the first edge that joins two equal colours proves an odd cycle.
Can the vertices be split into two groups so that every edge crosses between them? Colour a start vertex 0, give each neighbour the opposite colour by BFS, and keep going. If an edge ever joins two vertices of the same colour, the graph has an odd cycle and is not bipartite.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 12, with their answers.
Edge 0 (0 is colour 0) to 1. What does the check find?
Answer: Uncoloured: give it colour 1. A neighbour always gets the opposite colour.
Edge 0 (0 is colour 0) to 5. What does the check find?
Answer: Uncoloured: give it colour 1. A neighbour always gets the opposite colour.
Edge 1 (1 is colour 1) to 0. What does the check find?
Answer: Opposite colour: fine. Different colours across an edge is exactly the goal.
Edge 1 (1 is colour 1) to 2. What does the check find?
Answer: Uncoloured: give it colour 0. A neighbour always gets the opposite colour.
Edge 5 (5 is colour 1) to 0. What does the check find?
Answer: Opposite colour: fine. Different colours across an edge is exactly the goal.
Edge 5 (5 is colour 1) to 4. What does the check find?
Answer: Uncoloured: give it colour 0. A neighbour always gets the opposite colour.
Edge 2 (2 is colour 0) to 1. What does the check find?
Answer: Opposite colour: fine. Different colours across an edge is exactly the goal.
Edge 2 (2 is colour 0) to 3. What does the check find?
Answer: Uncoloured: give it colour 1. A neighbour always gets the opposite colour.
Edge 4 (4 is colour 0) to 3. What does the check find?
Answer: Opposite colour: fine. Different colours across an edge is exactly the goal.
Edge 4 (4 is colour 0) to 5. What does the check find?
Answer: Opposite colour: fine. Different colours across an edge is exactly the goal.
Edge 3 (3 is colour 1) to 2. What does the check find?
Answer: Opposite colour: fine. Different colours across an edge is exactly the goal.
Edge 3 (3 is colour 1) to 4. What does the check find?
Answer: Opposite colour: fine. Different colours across an edge is exactly the goal.
How it runs, step by step
Can the vertices be split into two groups so that every edge crosses between them? Colour a start vertex 0, give each neighbour the opposite colour by BFS, and keep going. If an edge ever joins two vertices of the same colour, the graph has an odd cycle and is not bipartite.
Bipartite check by two-colouring.
0 has no colour yet, so start a new component there: colour it 0 and queue it.
0 coloured 0.
From 0 (colour 0), 1 is uncoloured: give it 1 and queue it.
1 coloured 1.
From 0 (colour 0), 5 is uncoloured: give it 1 and queue it.
5 coloured 1.
From 1 (colour 1), 0 already has colour 0: opposite, as an edge requires.
Edge 1 to 0 crosses colours.
From 1 (colour 1), 2 is uncoloured: give it 0 and queue it.
2 coloured 0.
From 5 (colour 1), 0 already has colour 0: opposite, as an edge requires.
Edge 5 to 0 crosses colours.
From 5 (colour 1), 4 is uncoloured: give it 0 and queue it.
4 coloured 0.
From 2 (colour 0), 1 already has colour 1: opposite, as an edge requires.
Edge 2 to 1 crosses colours.
From 2 (colour 0), 3 is uncoloured: give it 1 and queue it.
3 coloured 1.
From 4 (colour 0), 3 already has colour 1: opposite, as an edge requires.
Edge 4 to 3 crosses colours.
From 4 (colour 0), 5 already has colour 1: opposite, as an edge requires.
Edge 4 to 5 crosses colours.
From 3 (colour 1), 2 already has colour 0: opposite, as an edge requires.
Edge 3 to 2 crosses colours.
From 3 (colour 1), 4 already has colour 0: opposite, as an edge requires.
Edge 3 to 4 crosses colours.
Every edge joins a 0 to a 1, so the graph is bipartite: group 0 is {0, 2, 4} and group 1 is {1, 3, 5}. One BFS, O(V + E).
Bipartite.
Remember
- Recursive DFS: the current path is the call stack; a vertex finishes only when everything below it has.
- Undirected cycle: a seen neighbour that is not the parent. Directed cycle: a neighbour still on the path.
- Bipartite: two-colour by BFS; an edge between equal colours means an odd cycle.
Topics covered
Where this is used
DatabasesDeadlock detection in PostgreSQL
When a backend has waited longer than deadlock_timeout, PostgreSQL builds a wait-for graph with a directed edge from each waiting backend to every backend holding the lock it wants. A cycle there means every process in the cycle is waiting on another member, so none of them can ever move, and the server aborts one with 'deadlock detected'. That check is the directed version on this page, run over a graph whose vertices are live backends.
CompilersImport cycles in the Go toolchain
Go compiles a package only after everything it imports, which is possible only if the import graph is acyclic. The toolchain loads imports depth first and keeps the chain of packages still open on the current path; an import that lands back on that chain stops the build with 'import cycle not allowed' followed by the chain itself. Printing the chain is possible because it is exactly the set of still-open frames, the grey vertices of this page.
Language runtimesTri-colour garbage collection
Concurrent collectors in Go and in the JVM sort objects into three colours: white for not yet reached, grey for reached but not yet scanned, black for scanned. The names line up with the directed check here, though grey means something wider: reached and pending, not only on one current path, because marking is driven by a worklist of grey objects rather than a single recursion. The guarantee is the same one. A black object is never scanned again, so a ring of references among live objects cannot loop the collector, and a ring of dead objects is simply never reached, which is why tracing reclaims reference cycles and reference counting alone cannot.
Scientific computingRed-black ordering in iterative solvers
A two-dimensional grid under a five-point stencil is a graph in which each point depends on its four neighbours, and that graph is bipartite: colour the points like a checkerboard and no red point ever touches another red point. Red-black Gauss-Seidel uses that two-colouring to update every red point in parallel and then every black one, so no two simultaneous updates read each other's half-written values. The safety of the parallel sweep rests entirely on the grid having no odd cycle.
Why it works this way
Why the directed check needs three states and not just visited
Meeting an already visited vertex in a directed graph is not enough to conclude anything. In 0 to 1, 0 to 2, 1 to 3, 2 to 3 the vertex 3 is reached twice and there is no cycle at all, so a two-state check would report one that does not exist. Only a neighbour that is still grey, meaning its call has not returned yet, is an edge back into the current path. Black means finished, and a finished vertex has no way back to you.
The parent check, and the edge it hides
Every undirected edge sits in both adjacency lists, so without the parent test the edge u-v would look like a cycle the instant v glanced back at u. Skipping the parent vertex fixes that, but it is wrong on a multigraph: two distinct edges between u and v really are a cycle of length two, and the parent test swallows it. If parallel edges are possible, remember the edge index you arrived on instead of the vertex.
One search is not the whole graph
Both cycle helpers take a start vertex and only ever see the component containing it, so a cycle sitting in a second, disconnected component is never reported. Real code wraps them in a loop over every vertex that is still unvisited, which is exactly what isBipartite already does with its loop over adj.indices. That outer loop is what turns the answer into a property of the graph rather than a property of the vertex you happened to start from.
Recursion depth is the length of the path
A graph shaped like a chain of 100,000 vertices means 100,000 nested calls that are all live at once, and a JVM thread with a typical stack of about a megabyte holds far fewer frames than that before it throws StackOverflowError. The exact ceiling is not a property of the algorithm: it moves with the platform, the thread, and how much each frame carries. Implementations that must survive real input stop depending on it, either by pushing frames onto an explicit stack or by running the search on a thread created with a stack size they chose.
Read more
- Depth-first searchWikipedia
- Checking a graph for acyclicity and finding a cyclecp-algorithms
- Bipartite graph checkcp-algorithms
- Bipartite graphWikipedia
- Round Trip IICSES 1678 · cses.fi