juniorGraph Theory

How do you detect a cycle in a directed graph?

Updated Feb 20, 2026

Short answer

Run a DFS while tracking two states per vertex: whether it has ever been visited, and whether it is on the current recursion stack. Encountering a vertex that is on the current stack means you have found a back edge, which is exactly a cycle. The alternative is Kahn's algorithm — perform a topological sort and, if fewer vertices come out than went in, the leftovers form a cycle. Both run in O(V+E).

Deep explanation

The subtlety that separates a correct answer from a plausible one is that a visited vertex is not evidence of a cycle in a directed graph. Consider A → B, A → C, B → D, C → D. DFS from A visits D via B, then reaches D again via C. D is visited, but there is no cycle — that is a cross edge, not a back edge.

You need three states, conventionally white (unvisited), grey (on the current recursion stack), and black (fully explored):

Python
WHITE, GREY, BLACK = 0, 1, 2


def has_cycle(graph):
    state = {v: WHITE for v in graph}


    def visit(v):
        state[v] = GREY                  # entering: on the current path
        for nbr in graph[v]:
            if state[nbr] == GREY:       # back edge -> cycle
                return True
            if state[nbr] == WHITE and visit(nbr):
                return True
        state[v] = BLACK                 # leaving: fully explored
        return False


    return any(state[v] == WHITE and visit(v) for v in graph)

Note the outer loop: a graph may be disconnected, so you must start a DFS from every unvisited vertex or you will miss cycles in components you never reach.

Kahn's algorithm answers the same question iteratively and avoids recursion depth limits:

Python
def has_cycle_kahn(graph):
    indeg = {v: 0 for v in graph}
    for v in graph:
        for nbr in graph[v]:
            indeg[nbr] += 1
    queue = deque(v for v in graph if indeg[v] == 0)
    removed = 0
    while queue:
        v = queue.popleft(); removed += 1
        for nbr in graph[v]:
            indeg[nbr] -= 1
            if indeg[nbr] == 0:
                queue.append(nbr)
    return removed != len(graph)   # leftovers are in a cycle

Prefer DFS colouring when you want to report the cycle — the grey vertices on the stack are the cycle itself. Prefer Kahn when you want a topological order anyway, or when the graph is deep enough to threaten the call stack.

For undirected graphs the rule is different: any visited neighbour that is not the immediate parent implies a cycle.

Real-world example

A build system must reject circular dependencies before it starts compiling.

Python
build_graph = {
    'app':   ['ui', 'auth'],
    'ui':    ['components'],
    'auth':  ['crypto', 'ui'],
    'components': ['utils'],
    'crypto': ['utils'],
    'utils': [],
}

No cycle here, so a topological order exists and the build proceeds bottom-up. If someone adds utils → app, DFS enters app (grey), descends to ui, components, utils, and from utils finds app still grey — the current path is app → ui → components → utils → app, reported verbatim as the offending cycle.

This is exactly how module bundlers surface circular imports and how package managers reject unsatisfiable dependency graphs.

Common mistakes

  • - Treating any visited vertex as a cycle, which produces false positives on cross edges and forward edges in a DAG.
  • - Forgetting to restart DFS from every unvisited vertex, so cycles in disconnected components go undetected.
  • - Never resetting a vertex from grey to black on exit, which corrupts the state for subsequent traversals.
  • - Applying the undirected rule — 'visited and not the parent' — to a directed graph, where the notion of parent does not constrain edges the same way.
  • - Recursing on a very deep graph and overflowing the stack
  • Kahn's algorithm or an explicit stack avoids it.
  • - Reporting only that a cycle exists when the caller needs to know *which* vertices form it, which the grey set gives you for free.

Follow-up questions

  • How does cycle detection differ for undirected graphs?
  • What is the relationship between cycle detection and topological sorting?
  • Can you detect a cycle without extra state per vertex?
  • How would you find every cycle rather than just one?

More Graph Theory interview questions

View all →