Cycle Detection in Graphs

DSA · Intermediate

Definition

Directed graphs use DFS colors (white/gray/black); undirected graphs check visited neighbors that are not the parent.

Detects deadlocks and impossible prerequisites.

Diagram

Flowchart

Example: Directed cycle

g = {0: [1], 1: [2], 2: [0]}
color = {}
def dfs(u):
    color[u] = 1
    for v in g[u]:
        if color.get(v) == 1 or (v not in color and dfs(v)): return True
    color[u] = 2
    return False
print(any(dfs(u) for u in g if u not in color))

Output: True

Complexity

O(V + E)

Key points

Union-Find also works for undirected graphs
Topological sort fails exactly when a cycle exists

Interview questions

Why gray, not just visited?

Visited-but-finished nodes do not form a cycle; only nodes on the current path do.