Cycle Detection — Why Two-Color DFS Fails on DAGs

Cycle detection comes up in dependency resolution (circular imports), task scheduling (deadlock detection), and graph algorithms (topological sort only works on DAGs). The approach differs between directed and undirected graphs, and the distinction matters — what looks like a cycle in an undirected graph might not be one in a directed graph. Here's the thing: get the color semantics wrong and you'll flag a cross edge as a cycle. That's a production-level bug that's quiet — your topological sort just silently fails.

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.

Here's the intuition: a cycle in a directed graph means you can follow edges and end up back where you started — that's a back edge in DFS language. In an undirected graph, any edge that connects two already-connected vertices creates a cycle — that's what Union-Find checks. And in a linked list, a cycle means following next pointers will loop forever — Floyd's algorithm catches that with no extra memory.

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.

Don't skip the initialization: Union-Find needs each node's parent to point to itself. For linked lists, make sure both pointers start at head — a common mistake is to start slow at head and fast at head.next, which still works but requires extra care with null checks.

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!

Now trace Floyd's on a linked list: 1→2→3→4→5→3 (cycle from 3). slow=1, fast=1 Step1: slow=2, fast=3 Step2: slow=3, fast=5 Step3: slow=4, fast=3 (fast moves from 5→3 via cycle) Step4: slow=5, fast=5 → meet at node 5. Cycle detected. To find the cycle start, reset slow=head (1), keep fast at 5, then move both one step each. They meet at node 3 — the cycle start.

Visualizing the DFS Tree and Back Edge in Directed Graphs

In a directed graph, a DFS traversal produces a spanning tree (the DFS tree) composed of tree edges. Edges that are not part of the tree fall into three categories: back edges (points to an ancestor in the DFS tree), forward edges (points to a descendant), and cross edges (points to a node in a different branch). Only back edges indicate a cycle because they create a circular path from descendant back to ancestor.

The back edge 3→1 completes the cycle 1→2→3→1. In contrast, if a cross edge 3→0 existed, it would not create a cycle because 0 is not on the current recursion stack (it's black). The diagram below illustrates the DFS tree with the back edge highlighted.

Cycle Extraction — Retrieving the Actual Cycle Vertices

Detecting a cycle is often not enough; you also need to output the vertices that form the cycle. In directed DFS, when you encounter a back edge to a gray node, the cycle consists of the nodes on the recursion stack from that gray node back to the current node. By maintaining a stack of the current DFS path, you can extract the cycle as soon as a back edge is found.

For undirected graphs, Union-Find can be extended to reconstruct the cycle by tracking parent edges during union. A simpler method: run DFS with parent tracking and, when a visited non-parent neighbor is found, trace back using the parent array to record the cycle. The parent array records the previous node on the current DFS path.

package io.thecodeforge.graph;

import java.util.*;

public class CycleExtraction {
    static final int WHITE = 0, GRAY = 1, BLACK = 2;
    List<Integer> cycle = new ArrayList<>();
    int[] color;
    int[] parent;
    List<Integer>[] adj;
    Deque<Integer> stack = new ArrayDeque<>(); // recursion stack

    public boolean hasCycleWithExtraction(List<Integer>[] adj) {
        this.adj = adj;
        int n = adj.length;
        color = new int[n];
        parent = new int[n];
        Arrays.fill(parent, -1);
        for (int i = 0; i < n; i++) {
            if (color[i] == WHITE) {
                if (dfs(i)) return true;
            }
        }
        return false;
    }

    private boolean dfs(int u) {
        color[u] = GRAY;
        stack.push(u);
        for (int v : adj[u]) {
            if (color[v] == GRAY) {
                // Back edge; extract cycle from stack
                cycle.clear();
                Iterator<Integer> it = stack.descendingIterator();
                while (it.hasNext()) {
                    int node = it.next();
                    cycle.add(node);
                    if (node == v) break;
                }
                Collections.reverse(cycle);
                return true;
            } else if (color[v] == WHITE) {
                parent[v] = u;
                if (dfs(v)) return true;
            }
        }
        stack.pop();
        color[u] = BLACK;
        return false;
    }

    public List<Integer> getCycle() {
        return cycle;
    }
}

BFS-Based Cycle Detection for Undirected Graphs

While Union-Find is elegant, BFS (or DFS) with parent tracking is another common approach for undirected graphs. BFS uses a queue and processes nodes level by level. The key insight: in an undirected graph, a cycle exists if, during BFS, we encounter a visited neighbor that is NOT the parent of the current node. Since the graph is undirected, each edge is traversable in both directions; the parent relationship prevents us from treating the edge we just came from as a cycle.

Algorithm: 1. Initialize visited array (boolean). 2. For each unvisited node, start BFS. 3. Mark node as visited and set its parent to -1. 4. For each neighbor of the current node: - If not visited, mark visited, set parent = current node, enqueue. - If visited and neighbor != parent, a cycle is detected. 5. If BFS completes without finding such a neighbor, no cycle in that component.

Time complexity: O(V+E) — same as DFS, but avoids recursion stack depth. Space: O(V) for the queue and parent array. For very wide graphs, BFS may use more queue memory than DFS stack but avoids stack overflow. BFS is particularly useful when you also want shortest paths or level information.

package io.thecodeforge.graph;

import java.util.*;

public class BFSCycleDetection {

    public static boolean hasCycleUndirected(List<Integer>[] adj) {
        int n = adj.length;
        boolean[] visited = new boolean[n];
        int[] parent = new int[n];
        Arrays.fill(parent, -1);

        for (int start = 0; start < n; start++) {
            if (visited[start]) continue;
            Queue<Integer> queue = new LinkedList<>();
            queue.add(start);
            visited[start] = true;
            while (!queue.isEmpty()) {
                int u = queue.poll();
                for (int v : adj[u]) {
                    if (!visited[v]) {
                        visited[v] = true;
                        parent[v] = u;
                        queue.add(v);
                    } else if (v != parent[u]) {
                        // visited and not parent -> cycle
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

C++ Implementations for Directed and Undirected Cycle Detection

C++ is widely used in performance-critical graph processing (e.g., game engines, trading systems). Here we provide two functions: one for directed graphs using three-color DFS, and one for undirected graphs using DFS with parent tracking. Both use adjacency lists and standard containers.

The directed variant uses a vector of int for colors: 0=WHITE, 1=GRAY, 2=BLACK. When a gray neighbor is found, a cycle is detected. The undirected variant uses a boolean visited array and an integer parent array; a cycle is detected when a visited neighbor is not the parent. Both functions are iterative in the sense that the recursion is depth-first (C++ compilers handle recursion well, but we also provide iterative alternatives in comments).

#include <vector>
#include <list>

enum Color { WHITE, GRAY, BLACK };

// Directed graph: returns true if cycle found
bool hasCycleDirected(const std::vector<std::list<int>>& adj) {
    int n = adj.size();
    std::vector<Color> color(n, WHITE);
    std::function<bool(int)> dfs = [&](int u) -> bool {
        color[u] = GRAY;
        for (int v : adj[u]) {
            if (color[v] == GRAY) return true;      // back edge
            else if (color[v] == WHITE && dfs(v)) return true;
        }
        color[u] = BLACK;
        return false;
    };
    for (int i = 0; i < n; ++i)
        if (color[i] == WHITE && dfs(i))
            return true;
    return false;
}

// Undirected graph: returns true if cycle found
bool hasCycleUndirected(const std::vector<std::list<int>>& adj) {
    int n = adj.size();
    std::vector<bool> visited(n, false);
    std::vector<int> parent(n, -1);
    std::function<bool(int)> dfs = [&](int u) -> bool {
        visited[u] = true;
        for (int v : adj[u]) {
            if (!visited[v]) {
                parent[v] = u;
                if (dfs(v)) return true;
            } else if (v != parent[u]) {
                return true;  // visited non-parent
            }
        }
        return false;
    };
    for (int i = 0; i < n; ++i)
        if (!visited[i] && dfs(i))
            return true;
    return false;
}

Advantages and Disadvantages of Each Algorithm

Each cycle detection algorithm has strengths and weaknesses. The table below summarizes the key trade-offs to help you choose the right tool for your production scenario.

For production systems, the choice often comes down to graph type and memory constraints. If your graph is directed and large, iterative DFS with three colors is the gold standard. For large undirected graphs, Union-Find is usually the fastest and most memory-efficient. For linked lists, Floyd's is the only sensible choice.

Practice Problems — Apply Cycle Detection Techniques

Sharpen your skills with these curated LeetCode and coding platform problems. They cover all three graph types and force you to choose the right algorithm. Attempt them after implementing the techniques above.

1. LeetCode 207: Course Schedule — Directed graph cycle detection using three-color DFS or Kahn's algorithm (BFS topo).
2. Hint: If a cycle exists, you can't finish all courses. Use adjacency list and detect back edges.
3. LeetCode 210: Course Schedule II — Return an order of courses (topological sort) if possible, else empty array.
4. Hint: Combine cycle detection with ordering. Kahn's algorithm works well here.
5. LeetCode 141: Linked List Cycle — Classic Floyd's tortoise-and-hare.
6. Hint: Use two pointers. Also try LeetCode 142 for cycle start.
7. LeetCode 684: Redundant Connection — Undirected graph with n nodes and n edges. Find the edge that creates a cycle.
8. Hint: Union-Find processes edges; the first edge whose endpoints are already connected is the answer.
9. LeetCode 802: Find Eventual Safe States — Directed graph; nodes that are not part of any cycle are safe.
10. Hint: Reverse the graph and do DFS with three colors to find nodes that are in cycles.
11. LeetCode 1192: Critical Connections in a Network — Find edges whose removal disconnects the graph (bridges).
12. Hint: Use DFS with discovery and low-link values (Tarjan's algorithm). Cycle detection helps identify non-bridge edges.
13. LeetCode 133: Clone Graph — Deep copy a graph with possible cycles.
14. Hint: Use DFS/BFS with a map from old to new node. Handle cycles by checking the map before recursing.

Start with Problems 1,3,4 to build confidence, then move to 2,5,6,7 for deeper understanding.