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.
Does this undirected graph contain a cycle? Run DFS remembering each vertex's parent, the vertex it was entered from. An edge to a vertex already seen is normal when that vertex is the parent, since every edge is seen from both ends. Any other seen vertex closes a cycle.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 6, with their answers.
At 0, the edge leads to 1. Is 1 unseen, the parent, or another seen vertex?
Answer: Unseen, enter it. 1 has not been visited, so the search goes deeper.
At 1, the edge leads to 0. Is 0 unseen, the parent, or another seen vertex?
Answer: The parent, ignore. 0 is where 1 was entered from, so this is the same edge again.
At 1, the edge leads to 2. Is 2 unseen, the parent, or another seen vertex?
Answer: Unseen, enter it. 2 has not been visited, so the search goes deeper.
At 2, the edge leads to 1. Is 1 unseen, the parent, or another seen vertex?
Answer: The parent, ignore. 1 is where 2 was entered from, so this is the same edge again.
At 2, the edge leads to 3. Is 3 unseen, the parent, or another seen vertex?
Answer: Unseen, enter it. 3 has not been visited, so the search goes deeper.
At 3, the edge leads to 1. Is 1 unseen, the parent, or another seen vertex?
Answer: Seen, a cycle. 1 was reached another way, so the edge 3-1 closes a loop.
How it runs, step by step
Does this undirected graph contain a cycle? Run DFS remembering each vertex's parent, the vertex it was entered from. An edge to a vertex already seen is normal when that vertex is the parent, since every edge is seen from both ends. Any other seen vertex closes a cycle.
Undirected cycle detection by DFS.
At 0, edge to 1. 1 is unseen, so enter it with parent 0.
Enter 1 from 0.
At 1, edge to 0. That is the parent, the edge 1 was entered by, seen from its other end. Ignore it.
Edge back to the parent 0, ignored.
At 1, edge to 2. 2 is unseen, so enter it with parent 1.
Enter 2 from 1.
At 2, edge to 1. That is the parent, the edge 2 was entered by, seen from its other end. Ignore it.
Edge back to the parent 1, ignored.
At 2, edge to 3. 3 is unseen, so enter it with parent 2.
Enter 3 from 2.
At 3, edge to 1. 1 is already seen and it is not 3's parent 2, so there are two different ways between 1 and 3: a cycle.
Edge 3 to 1 closes a cycle.
Cycle found through edge 3-1. The path from 1 down to 3 plus that edge is the loop. One DFS, O(V + E).
Cycle found.
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