Detecting Cycles in Graphs: The Three Interview Patterns

"Does this graph have a cycle?" shows up in course schedule, deadlock detection, and dependency questions. There are three standard approaches, and the right one depends on whether the graph is directed.

1. Directed graph: DFS with three colors

Mark each node as unvisited (0), in the current path (1), or finished (2). If you reach a node marked 1, you have found a back edge, which means there is a cycle.

def has_cycle_directed(n, edges):
    g = [[] for _ in range(n)]
    for u, v in edges:
        g[u].append(v)
    color = [0] * n
    def dfs(u):
        color[u] = 1
        for v in g[u]:
            if color[v] == 1 or (color[v] == 0 and dfs(v)):
                return True
        color[u] = 2
        return False
    return any(color[i] == 0 and dfs(i) for i in range(n))

2. Directed graph: Kahn's algorithm

Run a BFS topological sort. If you process fewer than n nodes, the leftover nodes are part of a cycle. This avoids recursion depth limits.

3. Undirected graph: union-find or parent tracking

With union-find, an edge whose two endpoints already share a root closes a cycle. With DFS, skip the edge back to the parent and flag any other visited neighbor.

Common mistakes

Written by the team at Linkjob, where we build AI tools for coding interview practice.