Cycle Detection in Graphs — DFS, Union-Find, and Floyd's Algorithm

What is Cycle Detection? — Plain English

A cycle in a graph is a path that starts and ends at the same node. Cycle detection is important in many algorithms: topological sort requires an acyclic graph (DAG), dependency resolution must detect circular dependencies, and deadlock detection in operating systems finds cycles in resource-allocation graphs. For directed graphs, we use DFS with three-color marking (white=unvisited, gray=in current path, black=done). For undirected graphs, Union-Find is simpler. For linked lists, Floyd's cycle detection (tortoise and hare) uses O(1) space.

How Cycle Detection Works — Step by Step

Directed graph cycle detection using DFS coloring: 1. Initialize all nodes as WHITE (unvisited). 2. For each WHITE node, start a DFS. 3. Mark node as GRAY (currently being explored) before visiting neighbors. 4. If we reach a GRAY neighbor, a back edge exists → cycle detected → return True. 5. After exploring all neighbors, mark node as BLACK (fully explored). 6. If DFS completes without finding a gray neighbor, no cycle through this path.

Undirected graph cycle detection using Union-Find: 1. For each edge (u,v), check if u and v are already in the same component (find(u) == find(v)). 2. If yes, adding this edge creates a cycle → return True. 3. If no, union the components and continue. 4. If all edges are processed without triggering step 2, no cycle exists.

Linked list cycle detection (Floyd's): 1. slow = fast = head. 2. Each step: slow moves 1, fast moves 2. 3. If fast or fast.next is None → no cycle. 4. If slow == fast → cycle exists.

Worked Example — Tracing Directed Graph Cycle Detection

Directed graph: 0→1→2→3→1 (cycle: 1→2→3→1). Edges: (0,1),(1,2),(2,3),(3,1).

DFS from 0: 1. Visit 0: color[0]=GRAY. Explore neighbor 1. 2. Visit 1: color[1]=GRAY. Explore neighbor 2. 3. Visit 2: color[2]=GRAY. Explore neighbor 3. 4. Visit 3: color[3]=GRAY. Explore neighbor 1. 5. Node 1 is GRAY → BACK EDGE found! Cycle detected. Return True.

Undirected example: edges (0,1),(1,2),(2,0). Union-Find: process (0,1): find(0)=0, find(1)=1, different → union. Process (1,2): different → union. Process (2,0): find(2)=0, find(0)=0, SAME → cycle detected!

Implementation

For directed graphs, maintain a color array (0=white,1=gray,2=black). DFS sets color to gray on entry and black on exit; finding a gray neighbor is a cycle. For undirected graphs, Union-Find checks connectivity before adding each edge. For linked lists, two pointers advance at different speeds — if they meet, a cycle exists. The DFS approach is O(V+E) time and O(V) space; Union-Find is O(E * alpha(V)) ≈ O(E) with path compression.

# Directed graph cycle detection (DFS coloring)
def has_cycle_directed(num_v, adj):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * num_v

    def dfs(v):
        color[v] = GRAY
        for nb in adj.get(v, []):
            if color[nb] == GRAY:   # back edge → cycle
                return True
            if color[nb] == WHITE and dfs(nb):
                return True
        color[v] = BLACK
        return False

    return any(dfs(v) for v in range(num_v) if color[v] == WHITE)

# Test directed
adj_d = {0:[1], 1:[2], 2:[3], 3:[1]}  # cycle 1->2->3->1
print(has_cycle_directed(4, adj_d))    # True

# Undirected graph cycle detection (Union-Find)
def has_cycle_undirected(num_v, edges):
    parent = list(range(num_v))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb: return True   # already connected → cycle
        parent[ra] = rb
        return False
    return any(union(u, v) for u, v in edges)

print(has_cycle_undirected(3, [(0,1),(1,2),(2,0)]))  # True
print(has_cycle_undirected(3, [(0,1),(1,2)]))         # False

Frequently Asked Questions