Coding Interviews

How do you detect a cycle in a directed graph?

By Interview Clozo · Published 27 October 2026 · Last verified 24 October 2026 · 15 min read

To detect a cycle in a directed graph, run a depth-first search (DFS) that marks each node white, grey or black, and report a cycle when an edge points to a grey node, one still on the current path. The costly mistake is the "seen before" shortcut from undirected graphs, which flags a harmless diamond (two paths that meet at one node), so watch for an edge to a grey node, not a node reached twice.

In this article

Before you start
Why interviewers ask this
Cycle detection in a directed graph from first principles
Worked example
Trade-offs and edge cases
How to answer it in an interview
Common mistakes
Follow-up questions
Sources

Before you start

Why interviewers ask this

Cycle detection decides whether work can be put in order at all. A build, a course plan or a chain of payments that loops back on itself has no valid order, so the program must find the loop before it does anything else. The same idea sits under deadlock detection, dependency checks in package managers and the question of whether a set of accounts passes money round in a circle.

Interviewers use it across coding interviews to separate candidates who memorised a template from those who understand why it works. A weak answer reuses the undirected-graph trick and flags any node it reaches twice. A strong answer keeps three states per node, explains why a grey node proves a loop, states the O(V + E) cost (V is the number of nodes, and a vertex is another word for a node; E is the number of edges) and says what happens on a graph with a very long path. This page builds that answer from zero.

Cycle detection in a directed graph from first principles

Cycle: A cycle is a path in a directed graph that starts and ends at the same node and follows the direction of every edge. A directed acyclic graph is a directed graph with no cycle, and only such a graph can be put in dependency order.
Back edge: A back edge is an edge found during a depth-first search that points from a node to one of its ancestors, a node still on the path the search is currently walking. In a directed graph a back edge exists exactly when a cycle exists.
Three-colour marking: Three-colour marking is a depth-first search bookkeeping scheme that labels each node white (not yet seen), grey (on the current path) or black (finished, with everything reachable from it explored), so a back edge can be recognised on sight.

In plain words

Picture a town of one-way streets. The junctions are the nodes and the streets are the edges. You walk with a ball of string tied to your waist and unroll it as you go. Every junction on your string is grey. A junction you have fully explored and left behind is black. A junction you have never seen is white. If a one-way street ever leads you back onto your own string, you have walked in a circle.

The analogy breaks in one place. When you rewind the string past a junction, it simply stops being grey. The string has no mark for junctions you finished, so you must chalk them yourself. That chalk mark is black, and it is why the method needs a third colour.

In one precise sentence: a directed graph has a cycle if and only if a depth-first search meets an edge that leads to a grey node. The Wikipedia article on cycles states the test as finding an edge that points to an ancestor of the current vertex.

The search turns A, B, D, E and C grey, meets grey D from C, and the parent chain gives the cycle.CC BY 4.0 — source: How do you detect a cycle in a directed graph?

Step-by-step description

The adjacency list maps each node to the nodes it points to.
Every node starts white, meaning not yet seen.
The walk greys A, B, D, E, C; the edge C to D hits grey D.
Parent pointers C, E, D, reversed and closed, give D, E, C, D.
Kahn, run on its own, orders only A and B, so a cycle exists.

An edge to a grey node, one on the current path, proves a cycle.
Kahn's algorithm cross-checks the verdict: only 2 of 5 nodes can be ordered on this graph.

Step 1: Store the graph as an adjacency list

An adjacency list is a table that maps each node to the list of nodes its edges point to, and it is the form that makes a graph walk fast. For the graph in this page, node A maps to B and C, B maps to D, C maps to D, D maps to E and E maps to C. In Python a dictionary of lists does the job, and defaultdict saves the check for a missing key.

Every node must appear as a key, even one with no outgoing edges, otherwise looking up its colour fails when an edge reaches it. The output of this step is the dictionary; the input is the list of edges. A hash table gives constant-time lookup of a node's neighbours, which the next steps rely on.

Step 2: Give every node a colour, all starting white

Three-colour marking stores one value per node, and every node starts white, meaning not yet seen. Use a dictionary from node to colour, or an array of 0, 1 and 2 when nodes are numbered.

White matters because it says "nothing is known about this node yet". Grey will mean "I am walking through this node right now", and black will mean "I finished this node and found no cycle through it". The input is the node list; the output is a colour table with every entry white. Without a third colour you cannot tell a node on your current path from a node you finished long ago, and Step 3 shows that this difference is the whole problem.

Step 3: Walk depth first and watch for an edge to a grey node

Depth-first search visits a node, turns it grey, then follows each outgoing edge in turn, and a cycle exists the moment an edge leads to a grey node. If the target is white, visit it and carry on. If it is black, skip it: that node is finished and cannot reach the current path, or a cycle through it would already have been reported. If it is grey, the target is an ancestor, so the edges from there down to here plus this edge form a loop.

Here is the trap. A node can be reached twice without any cycle. In the diamond A to B, A to C, B to D, C to D, node D is reached from B and again from C. A plain "seen before" check flags it. Three colours do not, because D is black by the time C looks at it, as the worked example below shows.¹ When a node's edges are exhausted, turn it black and return.

Step 4: Recover the cycle from parent pointers

A parent pointer is a record of which node the search came from. Parent pointers let the search return the cycle itself, not only a yes or no. Each time the search moves from u to a white node v, record parent[v] = u. When the edge from u to a grey node v appears, walk from u up the parent chain until you reach v, then reverse the list and append v.

Interviewers often ask for the loop because a circular dependency is useless without its members. In the worked graph the search stops at the edge from C to D and returns D, E, C, D.¹ The cost is one extra dictionary and a walk of at most the number of grey nodes. Python's standard library also returns the cycle: when TopologicalSorter finds one it raises CycleError, whose second argument is the list of nodes in the cycle with the first and last node the same (Python graphlib documentation, read 2026-10-24).

Step 5: Cross-check with Kahn's algorithm

Kahn's algorithm is a second, independent test: repeatedly remove a node that has in-degree zero, meaning no unprocessed node points to it, and the graph has a cycle exactly when some nodes can never be removed. Count each node's incoming edges first, put the zero-count nodes in a queue, then pop one, lower the in-degree of its neighbours and queue any that reach zero. If fewer nodes come out than went in, the leftovers are on a cycle or reachable from one.

This is the method of topological sort. The Wikipedia article on topological sorting states that if edges remain when no node with in-degree zero is left, the graph has a cycle, and that a topological order exists only when there is none. Kahn's algorithm cross-checks the verdict by counting how many nodes it can order. Use it as a check on the DFS result. DFS also gives an order: reversing the order in which nodes turn black is a valid topological order when no cycle exists.

Knowing it is half the job. Saying it is the other half.

Interview Clozo is an AI interview copilot for real interview rounds: it hears the question and puts a strong answer on your screen, and you say it in your own words. See the features or how it works.

Start Free Trial →

Worked example

Take the graph of the figure: five nodes and six edges, A to B, A to C, B to D, C to D, D to E and E to C.¹ Depth-first search visits the nodes in sorted order, so it starts at A and follows the first edge each time.

Node D has two parents, B and C, and that alone is not a cycle; the cycle is C to D to E to C, closed by the edge from C to D.CC BY 4.0 — source: How do you detect a cycle in a directed graph?

Text description of the diagram

Nodes C, D and E form the cycle.
Node D has two parents, B and C, and that alone is not a cycle.

The search turns A, B, D, E and C grey in that order and stops at the edge from C to D, because D is still grey.
Event	Colours after the event	What it means
enter A	A grey	the walk starts at A
enter B	A, B grey	A to B is a first-time edge to a white node
enter D	A, B, D grey	B to D
enter E	A, B, D, E grey	D to E
enter C	A, B, D, E, C grey	E to C reaches a white node
edge C to D	D is already grey	back edge, so a cycle

The cycle is D, E, C, D. Node D has two parents, B and C, and that alone is not a cycle. Kahn's algorithm agrees: the in-degrees are A 0, B 1, C 2, D 2 and E 1, so only A and then B can be removed, 2 of 5 nodes, and C, D and E are stuck.¹ Python's graphlib raises CycleError on the same graph and reports the same cycle list.¹

Now the diamond, A to B, A to C, B to D, C to D, which has no cycle. DFS enters A, B and D, finishes D and B, enters C, and finds D black, so it skips it; Kahn processes all 4 nodes. The naive check that flags any node reached twice reports an edge from C to D as a cycle, which is wrong.¹

The method in code:

def has_cycle(graph):
    colour = {n: 0 for n in graph}            # 0 white, 1 grey, 2 black
    for start in graph:
        if colour[start]:
            continue
        colour[start] = 1
        stack = [(start, iter(graph[start]))]
        while stack:
            node, edges = stack[-1]
            for nxt in edges:
                if colour[nxt] == 1:          # edge to a grey node
                    return True
                if colour[nxt] == 0:
                    colour[nxt] = 1
                    stack.append((nxt, iter(graph[nxt])))
                    break
            else:                             # all edges done
                colour[node] = 2
                stack.pop()
    return False

The code keeps its own stack (an explicit stack, in place of the call stack that recursion would use) of nodes and their iterators. An iterator is an object that hands out a node's edges one at a time, so a long path never deepens Python's call stack. The outer loop starts a new search from every white node, which covers graphs that are not connected. The run on a random acyclic graph of 1,000 nodes and 5,000 edges made exactly 1,000 node visits and 5,000 edge checks, which is nodes plus edges.¹

Trade-offs and edge cases

DFS and Kahn's algorithm both take time proportional to the nodes plus the edges, written O(V + E), because each node and edge is handled a constant number of times (Wikipedia, topological sorting). They differ in what they hand back and what can go wrong.

Pick DFS when you must return the cycle and Kahn when you want a queue-based method with no recursion.CC BY 4.0 — source: How do you detect a cycle in a directed graph?

Text description of the diagram

Both methods take time proportional to nodes plus edges.
DFS recovers the cycle through parent pointers while Kahn reports the stuck nodes.

Deep graphs break recursive DFS. The Python documentation says the recursion limit "prevents infinite recursion from causing an overflow of the C stack" (sys documentation, read 2026-10-24). On Python 3.12.12 the default limit is 1,000, and a recursive search on a chain of 5,001 nodes raised RecursionError; the iterative version above returned the right answer.¹ Convert to an explicit stack (a list you push to and pop from yourself), or use Kahn's algorithm, when a graph can be that deep.

A self-loop is a cycle. An edge from a node to itself finds that node grey, so the search reports it at once.¹

Disconnected graphs need the outer loop. A search started from one node never reaches the parts of the graph that node cannot reach. In a graph with P to Q and a separate loop R to S to R, a search from P alone sees no cycle; the outer loop over all nodes finds R, S, R.¹

Forgetting black gives false alarms. If a node is never turned black, it stays grey after its subtree is finished, and the next path that reaches it is flagged. On the cycle-free diamond that bug reports a cycle.¹

One cycle, not all of them. The search stops at the first back edge it finds, and the Python graphlib documentation (read 2026-10-24) says that when several cycles exist, only one undefined choice among them is reported. Listing every cycle is a harder problem and a different question.

Quotable facts for the cycle-detection answer, each from a source or from this page's script.
Fact	Value
Cycle test in a directed DFS	an edge to a grey node (a back edge)
Time for DFS or Kahn	proportional to V + E
Random acyclic graph, 1,000 nodes and 5,000 edges	1,000 node visits, 5,000 edge checks
Kahn on the worked graph	2 of 5 nodes ordered, so a cycle
Default Python recursion limit (3.12.12)	1,000
Recursive DFS on a 5,001-node chain	RecursionError