Cycle Detection in Directed Graphs using DFS

1. Why the Parent-Tracking Method Fails for Directed Graphs

In an undirected graph, if we're at node B and see a visited neighbor A from which we just came, it's not a cycle. It's just the other direction of the same edge.

In a directed graph, an edge A -> B does not imply an edge B -> A. If our DFS path is C -> A -> B, and from B we see an edge B -> A, this is a true cycle (A -> B -> A). The concept of a "parent" in the traversal doesn't help us distinguish a legitimate cycle from other path types.

A more complex scenario arises with "cross-edges." Imagine our DFS explores one branch completely (e.g., 0 -> 1 -> 2), and then backtracks to explore another branch (0 -> 3). If there's an edge from 3 to the already-visited node 1, is this a cycle? No, it's a cross-edge connecting two separate branches of the DFS tree. A simple visited check would incorrectly flag this as a cycle.

To understand this distinction visually and intuitively, the following video provides an excellent explanation.

2. The Two-State Tracking System: visited and recursion stack

The core insight from the video is that we need to detect when we loop back to a node that is an ancestor in the current path of exploration. We need to differentiate between:

1. A node visited in a previous, completed DFS branch.
2. A node visited in the current, active DFS branch.

To achieve this, we use two boolean arrays (or sets):

• visited[]: This array tracks every node that has ever been visited. Once a node is marked True, it stays True. This helps us avoid re-processing nodes and entire subgraphs that we know are cycle-free.
• recursionStack[] (also called pathVisited[] or visiting[]): This array tracks only the nodes that are currently in the recursion call stack for the active DFS traversal. A node is marked True when we enter its DFS function and marked False right before we exit (i.e., after exploring all its neighbors).

The rule for detecting a cycle is now simple and robust:

If our DFS traversal from a node u encounters a neighbor v that is already in the recursionStack (recursionStack[v] == True), we have found a back edge. This indicates a cycle.

The Three-Color Analogy

This two-array system is often described using a "three-color" analogy, which is great for conceptual understanding:

• WHITE: Unvisited node. (visited[i] == False and recursionStack[i] == False)
• GRAY: Node is currently being visited (in the recursionStack). (recursionStack[i] == True)
• BLACK: Node and all its descendants have been fully visited. (visited[i] == True and recursionStack[i] == False)

A cycle is found whenever the DFS encounters a GRAY node.

The "take U forward" video continues with a fantastic, detailed walkthrough of this exact algorithm.

3. Python Implementation and a Classic Interview Problem

With the logic clear, let's look at a standard Python implementation. This pattern is essential for your interview toolkit. The code below is adapted from the common structure for this problem.

def isCyclic(V, adj):
    visited = [False] * V
    recursion_stack = [False] * V

    # This loop handles disconnected components in the graph
    for node in range(V):
        if not visited[node]:
            if dfs(node, visited, recursion_stack, adj):
                return True # Cycle found
    
    return False # No cycle found in any component

def dfs(node, visited, recursion_stack, adj):
    # Mark the current node as visited and part of the recursion stack
    visited[node] = True
    recursion_stack[node] = True

    # Recur for all the neighbors
    for neighbor in adj[node]:
        # If neighbor is not visited, then recurse on it
        if not visited[neighbor]:
            if dfs(neighbor, visited, recursion_stack, adj):
                return True
        # If the neighbor is in the recursion stack, then a cycle is present
        elif recursion_stack[neighbor]:
            return True

    # The node is removed from the recursion stack before the function returns
    # This is the backtracking step
    recursion_stack[node] = False
    return False

You can also find this implementation and further explanation in the GeeksForGeeks article "Detect Cycle in a Directed Graph".

Application: LeetCode 207 "Course Schedule"

This algorithm isn't just theoretical; it's the direct solution to one of the most common graph interview questions. The problem asks if you can finish all courses given a set of prerequisites. For example, to take course 1, you must first take course 0 ([1, 0]).

This is a directed graph problem where courses are nodes and prerequisites are edges. Can you finish all courses? Yes, if and only if the graph has no cycles. A cycle like 0 -> 1 -> 0 means you can never satisfy the prerequisites.

4. Complexity Analysis

For any algorithm, analyzing its performance is key.

• Time Complexity: $O(V+E)$. This is the standard time complexity for a DFS traversal on a graph represented by an adjacency list. We visit each vertex (V) and each edge (E) at most once across all DFS calls.
• Space Complexity: $O(V)$.
  • The visited and recursion_stack arrays each take $O(V)$ space.
  • The depth of the recursion call stack can be at most $V$ in the worst case (a long chain).
  • Therefore, the total space is proportional to the number of vertices.

This analysis is also covered in the "take U forward" video from 15:30 to 16:15.

Conclusion

You've now learned the standard and efficient method for detecting cycles in directed graphs. This is a significant step up from the undirected case and a powerful pattern to have in your problem-solving toolkit.

Key Takeaways:

• Detecting cycles in directed graphs requires distinguishing between back edges (which form cycles) and cross edges.
• The standard approach uses a two-state system: one to track all visited nodes and another to track the recursion_stack (nodes in the current DFS path).
• A cycle is found when DFS encounters a neighbor that is already present in the recursion_stack.
• This algorithm runs in $O(V+E)$ time and $O(V)$ space and is the direct solution to popular interview questions like "Course Schedule."

Preview of the Next Lesson:

The concept of a cycle is fundamental to our next topic: Topological Sorting. A topological sort is a linear ordering of vertices such that for every directed edge u -> v, vertex u comes before vertex v in the ordering. Such an ordering is only possible if the graph is a Directed Acyclic Graph (DAG). In our next lesson, we will build upon today's work to implement algorithms that produce this ordering.