Cycle Detection in a Graph

Pseudocode

Directed and undirected graphs need genuinely different tests. The directed version tracks the recursion stack; the undirected version tracks the parent.

// Directed: three-colour DFS
WHITE = unvisited, GRAY = on recursion stack, BLACK = finished

hasCycle(u):
    color[u] = GRAY
    for each neighbor v of u:
        if color[v] == GRAY:  return true    // back edge
        if color[v] == WHITE and hasCycle(v): return true
    color[u] = BLACK
    return false

// Undirected: DFS carrying the parent
hasCycle(u, parent):
    visited.add(u)
    for each neighbor v of u:
        if v == parent: continue
        if v in visited: return true
        if hasCycle(v, u): return true
    return false

The distinction matters more than it looks. In a directed graph, reaching a BLACK node is a cross edge and is perfectly cycle free, so the naive visited check reports cycles that do not exist. In an undirected graph, skipping the parent is what stops every single edge from being read as a two-node cycle.

Worked example, step by step

Run the directed three-colour test on a graph that contains one cycle and one misleading cross edge.

Example graph: Directed edges A to B, A to C, B to D, C to D and D to B.

1. Enter A. color[A] = GRAY. Take the first neighbor, B.
2. Enter B. color[B] = GRAY. Its only neighbor is D.
3. Enter D. color[D] = GRAY. Its neighbor is B, and color[B] is GRAY. B is on the current recursion stack, so D to B is a back edge and the cycle B to D to B is confirmed.
4. What the naive version would do. Suppose there were no D to B edge. D would finish BLACK, control would unwind to A, and A to C to D would find D already visited. A plain visited check would call that a cycle. It is not: it is a cross edge into a finished subtree, and the three-colour test correctly ignores it because D is BLACK, not GRAY.

The graph does contain a cycle, B to D to B, found through the GRAY test. The A to C to D path is not a cycle, and only the colour distinction separates the two cases.

Complexity, and where it comes from

Time: O(V + E) · Space: O(V)

Both variants are a single DFS with constant extra work per edge, so the cost is the traversal cost. The colour array or visited set is O(V), plus O(V) recursion stack. The Union-Find alternative for undirected graphs runs in O(E alpha(V)), effectively linear, and is preferable when edges arrive one at a time and you want to reject a cycle-closing edge as it appears rather than rescanning the whole graph.

When to use Cycle Detection, and when not to

Pick the test that matches both the direction of your edges and whether the graph is static or streaming.

Common pitfalls

• Using the undirected test on a directed graph. This is the single most common bug in cycle detection. A plain visited check on a directed graph reports a cycle for any cross edge into an already finished subtree. Use three colours, or track the recursion stack as a separate set.
• Forgetting to reset the recursion-stack marker. The GRAY marker must be cleared to BLACK when the node finishes. Leaving nodes GRAY makes every later path into them look like a back edge, producing false positives on the second and subsequent DFS roots.
• Not restarting on disconnected components. One DFS from one source only sees one component. The cycle may sit in a component you never entered, so loop over all vertices and start a fresh DFS from each still-unvisited one.
• Self-loops and parallel edges. A self-loop is a cycle of length one and the parent check will not catch it. Two parallel edges between the same pair form a cycle of length two in an undirected multigraph, but skipping the parent unconditionally hides it. Skip the parent edge once, not every occurrence.

Frequently asked questions

How do you detect a cycle in a directed graph?

Run a DFS that colours nodes white, gray and black. A node is gray while it sits on the current recursion stack and black once it finishes. An edge into a gray node is a back edge and proves a cycle. An edge into a black node is a cross or forward edge and proves nothing. The whole test is O(V + E).

How do you detect a cycle in an undirected graph?

Run a DFS that carries the parent of each node. If you reach an already visited node that is not the parent, that edge closes a cycle. Alternatively use Union-Find: process edges one by one and report a cycle the first time both endpoints are already in the same set.

Why does the visited check fail on directed graphs?

Because being visited only means the node was reached earlier, not that it is an ancestor of the current node. In the graph A to B, A to C, B to D, C to D there is no cycle, yet a plain visited check flags the C to D edge because D was already seen through B. You need to know whether the target is still on the recursion stack.

What is the fastest way to detect a cycle?

For a static graph, a single DFS at O(V + E) is optimal since you must at least read the input. For an undirected graph built up edge by edge, Union-Find is better in practice because each added edge is tested in near constant time without retraversing.

Can a DAG contain a cycle?

No, by definition. A directed acyclic graph is precisely a directed graph with no cycles, which is why cycle detection is the standard validity check before topological sorting. If a cycle exists, no valid topological order exists.