Detect a Cycle in a Graph: Directed vs Undirected

"Does this graph contain a cycle?" sounds like a single question, but the answer depends on whether the edges have a direction. The same depth-first search that works perfectly on an undirected graph reports false cycles on a directed one, and the directed version reports a cycle on every edge of an undirected one. Knowing why is most of what an interviewer is checking.

The problem it solves

In a directed graph, a cycle is a path that follows edge directions and returns to its start: build → test → deploy → build. Finding one answers practical questions: can these tasks be scheduled at all, does this import chain loop, is this course plan possible? A directed graph with no cycle can be put in topological order; one with a cycle cannot.

In an undirected graph, a cycle is a closed path that uses each edge at most once. An undirected graph without cycles is a forest, and a connected one is a tree. Detecting a cycle there is the question "is this a tree?", or "would adding this cable create a loop in the network?".

The intuition

Start with a depth-first search and a visited set. In an undirected graph, meeting a visited node again usually means you found a second route to it — a cycle. There is one exception: the node you just came from. Every undirected edge can be walked back the way it came, and that is not a cycle. So you skip the parent and treat any other visited neighbour as proof of a cycle.

In a directed graph, that same test is wrong. Take four nodes with edges 0 → 1, 0 → 2, 1 → 3, 2 → 3. The search goes 0 → 1 → 3, finishes 3, and later reaches 3 again from 2. Node 3 is visited, but there is no cycle: both paths flow downhill. Reaching a visited node proves nothing unless that node is still on the current path.

Three colours capture exactly that:

• White: not visited yet.
• Grey: entered, and still on the current path — its descendants are not finished.
• Black: finished; every path from it has been explored.

An edge into a grey node is a back edge: it points to an ancestor on the current path, so the path loops. An edge into a black node is harmless, because nothing reachable from a black node leads back to the current path — otherwise that node would have found the cycle itself.

Watch it run

The animation runs the colouring on the lesson's build graph. build, test and deploy turn grey one after another as the search goes deeper. Then the edge deploy → build reaches a node that is still grey, and the cycle is found. The last frame points out docs, which nothing depends on: a black node could be met again safely; only grey is fatal.

The code

The three-colour check for directed graphs, next to the tempting one-flag version:

WHITE, GREY, BLACK = 0, 1, 2

def directed_has_cycle(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
    colour = [WHITE] * n

    def visit(u):
        colour[u] = GREY                       # on the current path
        for v in graph[u]:
            if colour[v] == GREY:              # back edge: the path loops
                return True
            if colour[v] == WHITE and visit(v):
                return True
        colour[u] = BLACK                      # finished, safe to meet again
        return False

    return any(colour[u] == WHITE and visit(u) for u in range(n))

def directed_visited_only(n, edges):           # the tempting version: one flag
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
    seen = [False] * n

    def visit(u):
        seen[u] = True
        for v in graph[u]:
            if seen[v] or visit(v):
                return True
        return False

    return any(not seen[u] and visit(u) for u in range(n))

diamond = [(0, 1), (0, 2), (1, 3), (2, 3)]     # two routes to 3, no loop
loop = [(0, 1), (1, 2), (2, 0)]
print(directed_has_cycle(4, diamond), directed_visited_only(4, diamond))   # False True
print(directed_has_cycle(3, loop), directed_visited_only(3, loop))         # True True

For undirected graphs, two options. A DFS that skips the parent, or union-find, which processes edges one at a time: if both ends are already in the same component, the new edge closes a loop.

def undirected_has_cycle(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    seen = [False] * n

    def visit(u, parent):
        seen[u] = True
        for v in graph[u]:
            if v == parent:
                continue                       # the edge we came in on
            if seen[v] or visit(v, u):
                return True
        return False

    return any(not seen[u] and visit(u, -1) for u in range(n))

def union_find_has_cycle(n, edges):
    root = list(range(n))

    def find(x):
        while root[x] != x:
            root[x] = root[root[x]]            # path halving
            x = root[x]
        return x

    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:                           # already connected: this edge closes a loop
            return True
        root[ru] = rv
    return False

path = [(0, 1), (1, 2), (2, 3)]
print(undirected_has_cycle(4, path), union_find_has_cycle(4, path))        # False False
print(undirected_has_cycle(4, path + [(3, 1)]), union_find_has_cycle(4, path + [(3, 1)]))   # True True

Each check is compared with a reference that uses a different idea. For directed graphs: Kahn's topological sort removes nodes with no incoming edges, and a cycle is exactly what stops it from removing all of them. For undirected graphs: a forest with c components has exactly n - c edges, so more edges than that means a cycle. The test uses 3,000 random graphs of each kind, with self-loops allowed in the directed ones:

import random
from collections import deque

def kahn_leftover(n, edges):                   # directed reference: topological sort
    indeg = [0] * n
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        indeg[v] += 1
    queue = deque(u for u in range(n) if indeg[u] == 0)
    removed = 0
    while queue:
        u = queue.popleft()
        removed += 1
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    return removed < n                         # something never reached in-degree 0

def more_edges_than_forest(n, edges):          # undirected reference: count components
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    seen, components = [False] * n, 0
    for s in range(n):
        if not seen[s]:
            components += 1
            seen[s] = True
            stack = [s]
            while stack:
                for v in graph[stack.pop()]:
                    if not seen[v]:
                        seen[v] = True
                        stack.append(v)
    return len(edges) > n - components        # a forest has exactly n - components edges

random.seed(9)
ok, one_flag_wrong, cyclic = True, 0, 0
for _ in range(3000):
    n = random.randint(1, 8)
    pairs = [(u, v) for u in range(n) for v in range(n)]
    directed = random.sample(pairs, random.randint(0, min(len(pairs), 10)))
    truth = kahn_leftover(n, directed)
    ok &= directed_has_cycle(n, directed) == truth
    one_flag_wrong += directed_visited_only(n, directed) != truth
    simple = [(u, v) for u, v in pairs if u < v]
    undirected = random.sample(simple, random.randint(0, len(simple) // 2))
    truth = more_edges_than_forest(n, undirected)
    cyclic += truth
    ok &= undirected_has_cycle(n, undirected) == truth == union_find_has_cycle(n, undirected)
print(ok, one_flag_wrong, cyclic)              # True 401 603

All three correct checks agree with their references. The one-flag directed check is wrong on 401 of the 3,000 directed graphs, every time by reporting a cycle that is not there.

The complexity

Both DFS versions visit each node once and look at each edge once (twice for undirected edges, once from each end): O(V + E) time and O(V) extra space for the colours and the recursion. Union-find uses O(V) space and processes the edges in O(E log V) time with path halving alone, or in nearly linear time once union by size is added; it also works when edges arrive one at a time, which a DFS cannot do without starting over.

Where it goes wrong

• One visited flag on a directed graph. It confuses "finished earlier" with "on the path now". Shown above.
• Colours on an undirected graph. Store each undirected edge both ways and the colour check sees u → v → u and reports a cycle for a single edge. Undirected graphs need the parent check.
• Parallel edges. Two separate edges between the same pair form a cycle, but skipping the parent node skips both. If the input can repeat an edge, skip the parent edge by its index instead.
• Deep recursion. A long chain exceeds Python's default recursion limit of 1,000 frames; use an explicit stack for large inputs.

How to say it in an interview

"For a directed graph I run DFS with three colours. Grey means the node is on the current recursion path; an edge into a grey node is a back edge, and that's a cycle. Black nodes are finished and safe to meet again, which is why a single visited set would give false positives. For an undirected graph I skip the edge back to the parent and any other visited neighbour means a cycle, or I use union-find and check whether an edge joins two nodes already connected. Both are O(V + E)."

A cycle is also what makes topological sort fail, and components and cycles covers the union-find side in depth.