DFS Cycle Detection in Directed Graphs

1. Why the Undirected Algorithm Fails

In an undirected graph, an edge between u and v is a two-way street. In a directed graph, an edge u -> v is a one-way path. This fundamental difference breaks our previous algorithm.

Consider a simple directed graph where 1 -> 2, and we also have 0 -> 1 and 0 -> 2. If we start a DFS from 0, we might visit 1, then backtrack and visit 2. From node 0's perspective, both 1 and 2 are now "visited". But the path 0 -> 2 does not form a cycle, even though 2's neighbor 1 (if we had an edge 2 -> 1) was already visited via a different path. Simply checking if (visited[neighbor]) is not enough.

A cycle in a directed graph means we followed a path and ended up back at an ancestor in our current path of exploration. We need a way to track which nodes are part of the current "active" traversal.

The following video from the "take U forward" channel gives an excellent visual explanation of this problem.

2. The Solution: Tracking the Recursion Stack

As the video explains, the key is to know if we've encountered a node that is not just visited, but is also part of the current recursion stack (the current path we are exploring).

To achieve this, we use two boolean arrays:

1. visited[]: This array works just like before. Once a node is visited and its entire DFS traversal is complete, it stays marked as true. This helps us avoid re-processing entire sections of the graph, which is especially important for disconnected graphs.
2. pathVisited[] (also called recursionStack[] or recStack[]): This is the crucial new array. A node is marked true in pathVisited only while it is currently in our recursion call stack. When we enter the DFS function for a node, we mark it as true. When we are about to exit the function (after visiting all its neighbors), we mark it back to false.

The Algorithm

With these two arrays, our DFS logic becomes:

1. Start a DFS from a node u. Mark visited[u] = true and pathVisited[u] = true.
2. Iterate through all adjacent nodes v of u.
   • Case 1: v has not been visited.
     If visited[v] is false, make a recursive call dfs(v). If that recursive call ever returns true (meaning it found a cycle down the line), we propagate that true result all the way up.
   • Case 2: v has been visited.
     We now check pathVisited[v].
     • If pathVisited[v] is true, it means v is an ancestor in the current DFS path. We have found a back edge from u to v. This confirms a cycle. We return true.
     • If pathVisited[v] is false, it means v was visited in a completely separate DFS traversal. This is a "cross edge" and does not indicate a cycle. We do nothing.
3. If we finish the loop for all of u's neighbors without finding a cycle, it means there are no cycles originating from u in this path. Before returning, we backtrack by setting pathVisited[u] = false. Then we return false.

Let's see this algorithm in action.

3. Java Implementation

Now, let's translate this logic into a clean, interview-ready Java implementation. We'll use an adjacency list representation, as we have in previous lessons.

For a robust text-based explanation and a solid code example, the GeeksforGeeks article is a great reference.

Here is a complete Java code example based on the logic we've discussed. Note the main isCyclic function that loops through all vertices to handle disconnected graph components correctly.

import java.util.ArrayList;

public class DirectedCycleDFS {

    // Main function to check if a cycle exists in a directed graph
    public boolean isCyclic(int V, ArrayList<ArrayList<Integer>> adj) {
        boolean[] visited = new boolean[V];
        boolean[] pathVisited = new boolean[V]; // Same as recStack

        // Call the recursive helper function for all vertices to handle disconnected components
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (dfsCheck(i, adj, visited, pathVisited)) {
                    return true;
                }
            }
        }
        return false;
    }

    // Recursive helper function for DFS
    private boolean dfsCheck(int node, ArrayList<ArrayList<Integer>> adj, boolean[] visited, boolean[] pathVisited) {
        visited[node] = true;
        pathVisited[node] = true;

        // Traverse for all adjacent nodes
        for (int adjacentNode : adj.get(node)) {
            // Case 1: If the adjacent node is not visited yet
            if (!visited[adjacentNode]) {
                if (dfsCheck(adjacentNode, adj, visited, pathVisited)) {
                    return true; // Cycle detected in a deeper recursive call
                }
            }
            // Case 2: If the adjacent node has been visited AND it's on the current path
            else if (pathVisited[adjacentNode]) {
                return true; // Cycle detected
            }
        }

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

    public static void main(String[] args) {
        int V = 4;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }

        // Creating a graph with a cycle: 0 -> 1 -> 2 -> 0
        adj.get(0).add(1);
        adj.get(1).add(2);
        adj.get(2).add(0);
        adj.get(2).add(3); // Another edge to show traversal

        DirectedCycleDFS detector = new DirectedCycleDFS();
        if (detector.isCyclic(V, adj)) {
            System.out.println("Cycle detected.");
        } else {
            System.out.println("No cycle detected.");
        }

        // Creating a graph without a cycle
        ArrayList<ArrayList<Integer>> adjNoCycle = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adjNoCycle.add(new ArrayList<>());
        }
        adjNoCycle.get(0).add(1);
        adjNoCycle.get(0).add(2);
        adjNoCycle.get(1).add(3);
        adjNoCycle.get(2).add(3);

        if (detector.isCyclic(V, adjNoCycle)) {
            System.out.println("Cycle detected in the second graph.");
        } else {
            System.out.println("No cycle detected in the second graph.");
        }
    }
}

4. Complexity Analysis

The performance of this algorithm is straightforward and efficient.

• Time Complexity: O(V + E). This is because, in the worst case, we will visit every vertex (V) and traverse every edge (E) exactly once. The two boolean arrays give us constant-time lookups.
• Space Complexity: O(V).
  • O(V) for the visited array.
  • O(V) for the pathVisited array.
  • O(V) for the recursion call stack in the worst-case scenario (a long, chain-like graph).
  • Overall, the space complexity is linear with respect to the number of vertices.

Conclusion

Excellent work! You have now learned the standard and most common DFS-based algorithm for detecting cycles in a directed graph. This is a fundamental problem that builds upon your graph traversal skills and is a frequent topic in technical interviews.

Key Takeaways:

• Detecting cycles in a directed graph requires distinguishing between a visited node in a different traversal path and a visited node that is an ancestor in the current traversal path.
• The two-array approach, using visited and pathVisited (or recursionStack), effectively solves this.
• A cycle is found when your DFS encounters an adjacent node v for which pathVisited[v] is already true.
• The backtracking step—setting pathVisited[node] = false before a function returns—is crucial for the algorithm's correctness.
• The algorithm runs in O(V + E) time and uses O(V) space.

Preview of the Next Lesson:
Our next topic is 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. As you might guess, such an ordering is only possible if the graph has no directed cycles. A graph with no directed cycles is called a Directed Acyclic Graph (DAG). So, our work today is a direct prerequisite for understanding when a topological sort is even possible! We will explore two algorithms for performing this sort: one based on DFS and another based on BFS (Kahn's Algorithm).