Detecting Cycles in Directed Graphs

Welcome to our next lesson on graph traversals. In our last session, you mastered detecting cycles in undirected graphs by using a "parent-aware" DFS. You learned that when traversing an undirected graph, encountering a visited node isn't enough to declare a cycle; you must also ensure it's not the immediate parent you just came from.

Today, we shift our focus to directed graphs. The one-way nature of their edges introduces new challenges and requires a more nuanced approach than simply tracking a parent. The parent-aware method is insufficient here. Why? Because in a directed graph, finding a path back to a previously visited node that isn't your immediate parent is the very definition of a cycle.

This lesson will equip you with a robust DFS-based technique to handle this. We will introduce the concept of node visitation states, which allows our traversal to distinguish between a path that has been fully explored and one that is currently in progress. By the end of this lesson, you'll be able to implement this algorithm to confidently detect cycles in any directed graph.

Why Parent-Aware Is Not Enough

Consider a simple directed graph: A -> B -> C. If we add an edge from C back to A, we create a cycle: A -> B -> C -> A.

Let's trace this with our old parent-aware DFS, starting at A:

1. dfs(A, parent=-1): Mark A as visited.
2. dfs(B, parent=A): Mark B as visited.
3. dfs(C, parent=B): Mark C as visited.
4. From C, we see its neighbor A.
   • Is A visited? Yes.
   • Is A the parent of C? No, C's parent is B.

In the undirected case, this condition signaled a cycle. Here, it also correctly identifies one. But what about a more complex, non-cyclic graph like A -> B, A -> C, C -> B?

1. dfs(A, parent=-1): Mark A as visited.
2. Explore neighbor C: dfs(C, parent=A). Mark C as visited.
3. Explore neighbor B: dfs(B, parent=C). Mark B as visited.
4. B has no outgoing edges. Return.
5. Back at C, no more neighbors. Return.
6. Back at A, we now explore its other neighbor, B.
7. We see that B is already visited. Is B the parent of A? No. According to the undirected rule, this would be a cycle. But it's not. It's a "cross edge" that leads to a part of the graph we've already explored through a different path.

We need a way to tell the difference between a back edge (one that leads back to an ancestor in the current traversal path, forming a cycle) and other types of edges that might lead to already visited nodes.

The Three-State Solution: White, Gray, and Black Sets

The standard and most intuitive solution is to track the state of each node using three "colors":

• WHITE: The node is unvisited.
• GRAY: The node has been visited and is currently in our recursion stack. This means we are actively exploring paths originating from this node.
• BLACK: The node and all its descendants have been fully explored. We are done with it.

The algorithm works as follows: we perform a DFS, and for each node we visit, we move it from the WHITE set to the GRAY set. We explore all its neighbors. After we have explored all paths from that node, we move it from the GRAY set to the BLACK set.

The rule for detecting a cycle is simple and powerful: If, during our traversal, we encounter a GRAY node, we have found a back edge and thus a cycle.

The article from GeeksforGeeks provides a concise explanation of this idea, linking it to the concept of "back edges" in a DFS tree.

To see this logic in motion, the following classic video by Tushar Roy provides an excellent, detailed walkthrough. He methodically moves nodes between the white, gray, and black sets, making the process very clear.

From Concept to Implementation

While the white/gray/black model is perfect for conceptual understanding, in code, we typically implement this using two boolean arrays:

1. visited: An array to keep track of all nodes visited in the entire DFS process. This helps us avoid re-processing disconnected components. A node is marked true and stays true.
2. recursionStack (or pathVis): An array to track only the nodes in the current recursion path. This corresponds to the gray set. A node is marked true when we enter its recursive call and false when we exit.

Here is the updated logic using these two arrays:

• Start DFS from a node. Mark visited[node] = true and recursionStack[node] = true.
• For each neighbor:
  • If recursionStack[neighbor] is true, we have found a path back to a node in the current call stack. A cycle is detected.
  • If visited[neighbor] is false, it's a new node for this path. Recurse on it. If the recursive call finds a cycle, propagate true back up.
• After exploring all neighbors of node (i.e., after the for loop finishes), we are leaving this node's recursive call. We must mark recursionStack[node] = false. This backtracking step is crucial; it removes the node from the "active path" set.

This image nicely illustrates the state of these arrays during a traversal. pathvis is what we are calling recursionStack.

Application: The "Course Schedule" Problem

This algorithm isn't just a theoretical exercise; it's the direct solution to one of the most common graph interview problems, "Course Schedule" (LeetCode 207). The problem asks if you can finish all courses given a list of prerequisites. A prerequisite [A, B] means you must take course B before A, forming a directed edge B -> A. If there is a cycle in these prerequisites (e.g., A requires B, B requires C, and C requires A), it's impossible to complete the courses.

The following video from NeetCode explains exactly how to model this problem and apply the DFS cycle detection algorithm we've just learned.

TypeScript Implementation

Let's consolidate this into a full TypeScript implementation. We'll use a main function to handle potentially disconnected components and a DFS helper that uses the visited and recursionStack arrays. This code is adapted from the JavaScript example provided by GeeksforGeeks.

Here is a TypeScript version using visited and recursionStack arrays:

/**
 * Detects if a cycle exists in a directed graph.
 * @param numNodes The total number of nodes (labeled 0 to numNodes-1).
 * @param edges An array of pairs [u, v] representing an edge from u to v.
 * @returns true if a cycle exists, false otherwise.
 */
function hasCycleDirected(numNodes: number, edges: number[][]): boolean {
    // Build adjacency list
    const adj = Array.from({ length: numNodes }, () => []);
    for (const [u, v] of edges) {
        adj[u].push(v);
    }

    const visited: boolean[] = new Array(numNodes).fill(false);
    const recursionStack: boolean[] = new Array(numNodes).fill(false);

    function hasCycleUtil(node: number): boolean {
        // Mark node as visited and add to current recursion path
        visited[node] = true;
        recursionStack[node] = true;

        for (const neighbor of adj[node]) {
            // If the neighbor is in the current recursion stack, a cycle is found.
            if (recursionStack[neighbor]) {
                return true;
            }

            // If neighbor is unvisited, recurse.
            // If the recursive call finds a cycle, propagate the result up.
            if (!visited[neighbor]) {
                if (hasCycleUtil(neighbor)) {
                    return true;
                }
            }
            // If neighbor is visited but not in recursionStack, it's a cross edge
            // to a fully explored part of the graph. We do nothing.
        }

        // Backtrack: remove node from the current recursion path
        recursionStack[node] = false;
        return false;
    }

    // Iterate through all nodes to handle disconnected components.
    for (let i = 0; i < numNodes; i++) {
        if (!visited[i]) {
            if (hasCycleUtil(i)) {
                return true;
            }
        }
    }

    return false;
}

// Example with a cycle: 0 -> 1 -> 2 -> 0
const edgesWithCycle = [[0, 1], [1, 2], [2, 0]];
console.log(hasCycleDirected(3, edgesWithCycle)); // Output: true

// Example without a cycle: 0 -> 1 -> 2
const edgesWithoutCycle = [[0, 1], [1, 2]];
console.log(hasCycleDirected(3, edgesWithoutCycle)); // Output: false

Complexity Analysis

• Time Complexity: $O(V+E)$, where $V$ is the number of vertices and $E$ is the number of edges. Each vertex is visited once, and every edge is considered once.
• Space Complexity: $O(V)$. This is for the visited and recursionStack arrays, each of size $V$, and for the depth of the recursion call stack, which can be up to $V$ in the worst case (e.g., for a graph that is a single long chain).

Conclusion

You have now extended your graph traversal toolkit to handle cycle detection in directed graphs. This is a significant step, as it moves beyond simple connectivity and into analyzing the structural properties of a graph.

Key Takeaways:

• The Problem: Parent-aware DFS is insufficient for directed graphs because it can't distinguish between a "back edge" (which forms a cycle) and a "cross edge" to an already explored branch.
• The Solution: Augment DFS with a three-state system (white, gray, black) to track node status.
• The Core Logic: A cycle is detected when the traversal encounters a node that is currently being visited (a "gray" node, or one in the active recursionStack).
• The Implementation: This is commonly implemented using two boolean arrays: one to track all visited nodes (visited) and another to track nodes in the current recursive path (recursionStack).
• The Backtrack Step: Removing a node from the recursionStack after exploring its descendants is the most critical step in the implementation.

The concept you've learned today is fundamental. It's the key to solving problems like "Course Schedule" and is a prerequisite for our next topic: Topological Sorting. A topological sort provides a linear ordering of vertices in a Directed Acyclic Graph (DAG). You'll see that the very first step in any topological sort algorithm is to ensure the graph is, in fact, acyclic.