Cycle Detection in Directed Graph, in depth: three-colour DFS that returns the cycle, an explicit-stack version for deep graphs, Kahn leftovers, all cycles via SCCs and where it runs in production

Why the undirected trick fails

In an undirected graph, any edge from the current vertex to an already visited vertex other than your parent closes a cycle. Applying the same rule to a directed graph gives false positives. Take edges A to B, A to C and C to B. A DFS from A visits B, finishes it, then visits C and finds the edge C to B pointing at a visited vertex. There is no cycle: there is no way to get from B back to C or A. B is simply reachable by two routes.

The fix is to distinguish visited vertices that are finished from visited vertices that are still on the current path. Only an edge back to a vertex on the current path means you can return to where you started.

Three colours

Give every vertex one of three colours. WHITE means not yet discovered. GRAY means discovered and still open: DFS entered it and has not yet returned from it, so it lies on the current recursion stack. BLACK means finished: every vertex reachable from it has been fully explored.

During DFS from u, look at each edge u to v. If v is WHITE, it is a tree edge: recurse. If v is GRAY, it is a back edge: v is an ancestor of u on the current path, so the path from v down to u plus the edge u to v is a cycle. If v is BLACK, it is a forward or cross edge, and it cannot close a cycle, because if a path led from v back to u, DFS would have discovered u while v was still GRAY.

That last argument is the whole correctness proof, and it gives the theorem: a directed graph has a cycle if and only if DFS finds a back edge. Each vertex and edge is examined once, so the cost is O(V + E) time and O(V) extra space, the same as plain DFS. Edge classification in general is treated in the traversal guide; here we only need the GRAY test.

Returning the cycle, not just a boolean

To report the cycle, record each vertex's DFS parent. When the back edge u to v is found, walk parent pointers from u until you reach v; reversed, that list is the path from v to u, and appending v closes the loop.

WHITE, GRAY, BLACK = 0, 1, 2

def find_cycle(graph):
    # graph: dict vertex -> list of successors. Returns a cycle [v0, ..., v0] or None.
    color = {v: WHITE for v in graph}
    parent = {}

    def dfs(u):
        color[u] = GRAY
        for v in graph.get(u, ()):
            if color.get(v, WHITE) == WHITE:
                parent[v] = u
                cycle = dfs(v)
                if cycle:
                    return cycle
            elif color[v] == GRAY:             # back edge u -> v
                path = [u]
                while path[-1] != v:
                    path.append(parent[path[-1]])
                path.reverse()
                return path + [v]
        color[u] = BLACK
        return None

    for s in graph:
        if color[s] == WHITE:
            cycle = dfs(s)
            if cycle:
                return cycle
    return None

The outer loop matters: a graph can have several disconnected regions, and a cycle may live in a part unreachable from the first start vertex. The graph.get(u, ()) and color.get(v, WHITE) calls tolerate vertices that appear only as edge targets, which is common when the graph is built from dependency declarations where leaves are never declared themselves.

A worked example

Consider a small build graph: app -> [auth, ui], auth -> [session, crypto], session -> [app], ui -> [crypto], crypto -> []. Trace the recursive detector from app.

1. app becomes GRAY. Its first successor auth is WHITE: parent[auth] = app, recurse.
2. auth becomes GRAY. Its first successor session is WHITE: parent[session] = auth, recurse.
3. session becomes GRAY. Its only successor app is GRAY. Back edge found from session to app.
4. Walk parents from session: session, then parent[session] = auth, then parent[auth] = app, which equals the target. Reverse to app, auth, session and append app.

The function returns ['app', 'auth', 'session', 'app']. Note what it does not do: it never visits ui or crypto, because it stops at the first cycle. That is the right default for a validation error. If you remove the session to app edge, the same run turns session, crypto, auth, ui and app BLACK in that order and returns None. Because edges point from a target to what it needs, that finishing order is a valid build order, dependencies first, and its reverse is a topological order of the edges, which is exactly why cycle detection and topological sorting are usually the same pass.

When recursion is not an option

Recursive DFS uses one stack frame per vertex on the current path. CPython's default recursion limit is 1,000, and a JVM thread's default stack holds a few thousand to tens of thousands of frames depending on frame size. A dependency chain of 50,000 migrations or a long linked structure will crash the recursive version. Raising the limit only moves the crash, and in CPython can take down the interpreter instead of raising a clean exception.

The fix is to manage the stack yourself. Each stack entry holds a vertex and an iterator over its remaining successors, so resuming a vertex continues where it left off. That detail is what makes it a true DFS; pushing all successors at once and popping them later gives a different visiting order and breaks the GRAY invariant.

def find_cycle_iter(graph):
    color = {v: WHITE for v in graph}
    for s in graph:
        if color[s] != WHITE:
            continue
        stack = [(s, iter(graph.get(s, ())))]   # the explicit recursion stack
        color[s] = GRAY
        while stack:
            u, it = stack[-1]
            advanced = False
            for v in it:
                c = color.get(v, WHITE)
                if c == WHITE:
                    color[v] = GRAY
                    stack.append((v, iter(graph.get(v, ()))))
                    advanced = True
                    break
                if c == GRAY:                  # v is somewhere on the stack
                    path = [x for x, _ in stack]
                    return path[path.index(v):] + [v]
            if not advanced:
                color[u] = BLACK
                stack.pop()
    return None

Here the stack itself is the current path, so the cycle is just the slice from v to the top. The path.index(v) scan is linear in the path length, but it runs once, when the cycle is found, so the total stays O(V + E). For very large graphs, also map vertex labels to dense integers and store colours in an array; dictionaries of strings dominate memory long before the algorithm does.

The in-degree method (Kahn) and its leftovers

A second approach needs no DFS. Count each vertex's in-degree, repeatedly remove vertices whose in-degree is zero and decrement their successors, and see whether every vertex was removed. A vertex in a cycle can never reach in-degree zero, because one of its predecessors is also in the cycle and never gets removed.

from collections import deque

def kahn_leftover(graph):
    indeg = {v: 0 for v in graph}
    for u in graph:
        for v in graph[u]:
            indeg[v] = indeg.get(v, 0) + 1
    queue = deque(v for v, d in indeg.items() if d == 0)
    seen = 0
    while queue:
        u = queue.popleft()
        seen += 1
        for v in graph.get(u, ()):
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    return {v for v, d in indeg.items() if d > 0}   # empty set means acyclic

The leftover set is useful but easy to misread. It contains every vertex on a cycle and also every vertex downstream of one. In the worked example no vertex starts with in-degree zero, because app is fed by session, so Kahn removes nothing and all five vertices are left over, including ui and crypto, which are not on the cycle at all. The leftovers tell you which part of the graph is stuck, not what the cycle is. To produce a witness, run the DFS detector restricted to the leftover vertices, which is cheap because the set is usually small.

Choose Kahn when you need a schedule anyway and want layer-by-layer parallelism (every vertex in the queue at once can run concurrently), and DFS when you want the witness directly or the graph is generated lazily.

Every cycle: strongly connected components

First-cycle-found is the right answer for validation, but sometimes you want the full picture: which modules are tangled together. Partition the graph into strongly connected components, maximal sets where every vertex can reach every other. Every cycle lies entirely inside one component, and a component of more than one vertex, or a single vertex with a self-loop, contains at least one cycle. Tarjan's and Kosaraju's algorithms both find all components in O(V + E); Kosaraju's algorithm in depth walks through one.

Report each non-trivial component as a tangle and run the witness detector inside it to show one concrete loop. Do not try to list every simple cycle: their number can grow exponentially with graph size, and Johnson's algorithm for enumerating them is output-sensitive, so it is only practical on small components.

Where it runs in production

Build systems and task runners check the target graph before execution and print the witness path. Package managers check requirement graphs; some ecosystems refuse cycles outright while others allow them and must load the whole component together. Database engines maintain a wait-for graph, with an edge from each transaction to the one holding a lock it needs; a cycle is a deadlock, and the engine aborts one victim in it. Workflow orchestrators reject cyclic DAG definitions at load time. Spreadsheet engines report circular references with the cells involved.

Many of these graphs change one edge at a time, so re-running a full DFS per edit is wasteful. The cheap incremental check is: before adding u to v, test whether u is reachable from v. If it is, the new edge would close a cycle, and the path you found is the witness. This costs one search per insertion and keeps the invariant that the stored graph is always acyclic. Cycles of a different kind, a linked list or an iterated function looping, are a separate problem with constant-memory solutions, covered in Floyd's cycle detection.

Failure modes

Real detectors fail in predictable ways.

• Two-state visited sets that report false cycles on diamond-shaped graphs, as in the undirected trick above.
• Starting DFS only from a root and missing cycles in parts of the graph it cannot reach.
• Forgetting self-loops; the colour test handles them naturally (u is GRAY when it sees itself), but hand-rolled shortcuts often skip edges where u equals v.
• Recursion overflow on deep but perfectly valid acyclic graphs, which surfaces as a crash in production long after tests on small graphs passed.
• Reporting the Kahn leftovers as the cycle and sending users to fix vertices that are merely downstream.
• Non-deterministic output: iterating unordered sets makes the reported cycle differ between runs, which confuses users and flakes tests. Sort successors or preserve declaration order.

What to do next

1. Implement the recursive detector and run it on the worked example, then on the diamond A to B, A to C, C to B to confirm no false positive.
2. Generate a chain of 100,000 vertices and confirm the recursive version fails and the iterative one succeeds.
3. Write a property test: for random graphs, every returned path must start and end at the same vertex and use only real edges; when None is returned, a topological order must exist.
4. Add Kahn's method and check that its leftover set is empty exactly when DFS returns None.
5. In a build or dependency tool you own, make the cycle error print the witness path in declaration order.
6. Read up on strongly connected components and report tangles per component for large graphs.