Cycle Detection in Directed Graphs with DFS

Recommended resources

The freely available resources this lesson will direct you to.

Welcome back! In our previous lessons, we explored how to apply topological sorting to various problems, assuming the input graph was a Directed Acyclic Graph (DAG). But a crucial question remains: what if it's not? A single cycle in a dependency graph can render a task schedule impossible, so detecting such cycles is a fundamental problem in its own right.

This lesson focuses on a direct and powerful method for this task: detecting a cycle in a directed graph using a modified Depth-First Search (DFS). You'll learn why the standard DFS for undirected graphs falls short here and master a three-state tracking technique that is essential for many graph-based interview questions.

By the end of this lesson, you will be able to implement a robust, DFS-based algorithm to determine if a directed graph contains a cycle.

The Challenge of Directed Cycles: Introducing Back Edges

In an undirected graph, finding a cycle with DFS is relatively straightforward: if you encounter an already-visited node that isn't your immediate parent, you've found a cycle. This logic doesn't work for directed graphs. Consider an edge u -> v and another separate path from u to v. A simple visited-check would falsely flag a cycle.

The key to detecting cycles in directed graphs is identifying a specific type of edge: a back edge. A back edge is an edge that leads from a node to one of its own ancestors in the current DFS recursion path.

In the graph on the right, the red 'X's mark back edges. The edge from 1 to 2, for instance, points from a node back to an ancestor (2) in the current search path, forming a cycle. The self-loop at node 3 is also a back edge.

To understand the concept of a back edge and why it's the definitive sign of a cycle, let's first see why the simple approach fails and what "on the same path" truly means. The following video provides an excellent intuition.

G-19. Detect cycle in a directed graph using DFS | Java | C++

This video from take U forward begins by perfectly illustrating why the cycle detection method for undirected graphs is insufficient for directed graphs.

Watch the initial segment that explains why the standard method fails. The key takeaway is the idea that a cycle exists only if we revisit a node on the current path.

With this intuition, we can formalize the idea of a back edge. The following resource gives a concise definition.

Detect Cycle in a directed graph using colors

This article from GeeksforGeeks formally defines back edges within the context of a DFS traversal.

Read the section titled Understanding Back Edges. This will solidify the connection between finding a back edge and proving the existence of a cycle.

The Three-State Solution: Visited, Visiting, Unvisited

To detect a back edge, we need to know more than just whether a node has been visited at some point. We need to know if it's part of the current active recursion path. This leads to a classic three-state (or "coloring") approach for each node:

UNVISITED (or WHITE): The node has not been reached yet.
VISITING (or GRAY): The node is currently in the recursion stack. We have started a DFS from this node, but we haven't finished exploring all its descendants yet.
VISITED (or BLACK): The node and all its descendants have been fully explored. The DFS call for this node has completed.

The algorithm works as follows:

We start a DFS from an UNVISITED node and immediately mark it as VISITING.
We explore its neighbors.
If we encounter a neighbor that is currently in the VISITING state, we have found a back edge! A cycle exists.
If we encounter an UNVISITED neighbor, we recurse on it.
If we encounter a VISITED neighbor, we do nothing. That part of the graph has already been cleared and contains no cycles involving the current path.
After exploring all neighbors of a node and returning from all recursive calls, we mark the node as VISITED. This signifies that it is leaving the recursion stack.

This is a fundamental pattern for directed graph problems. You can implement it either with an integer array to hold the three states (e.g., 0, 1, 2) or with two boolean arrays, which we'll explore next.

Implementation with Two Arrays: `visited` and `recursionStack`

A common and clear way to implement the three-state logic is with two boolean arrays:

visited[]: This tracks if a node has ever been visited (equivalent to a node being VISITING or VISITED).
recursionStack[] (or pathVisited[]): This tracks if a node is currently in the recursion stack (equivalent to a node being VISITING).

The algorithm begins with all nodes unvisited and the recursion stack empty. The two arrays, `visited[]` and `recStack[]`, track the state of the traversal.

The logic, rephrased with these two arrays, is:

When starting DFS for node: visited[node] = true, recursionStack[node] = true.
For each neighbor of node:
- If !visited[neighbor], recurse: dfs(neighbor). If this call returns true (cycle found), propagate true up.
- Else if recursionStack[neighbor], a cycle is found! This is the back edge condition. Return true.
When returning from DFS for node: recursionStack[node] = false. This is the crucial backtracking step, removing the node from the current path.

The following video provides an exceptionally clear, step-by-step walkthrough of this exact process.

G-19. Detect cycle in a directed graph using DFS | Java | C++

The same video from take U forward now provides a full walkthrough of the two-array algorithm.

Watch the detailed explanation of the two-array algorithm. Pay close attention to when pathVisited (our recursionStack) is marked true and when it is marked false. This is the heart of the algorithm.

Full Implementation and Analysis

Now let's put it all together by studying a complete implementation. The problem "Course Schedule" on LeetCode is a classic application of this pattern—you can take all courses if and only if there are no cycles in the prerequisite graph.

The video below frames the problem this way and provides another excellent dry run using the three-state (coloring) method.

Course Schedule (Detecting Cycles in a Graph) - Leetcode 207 - Graphs (Python)

This video from Greg Hogg solves LeetCode 207 "Course Schedule," which is exactly the problem of detecting a cycle in a directed graph.

First, watch the problem setup to see how a real-world problem maps to cycle detection. Next, understand the three states (unvisited, visiting, visited), which is the coloring approach. Then, follow the walkthrough where a cycle is found. Notice how the algorithm terminates as soon as it hits a node that is currently in the "visiting" state. Finally, review the Python implementation and complexity analysis to see how these concepts translate to code.

To round out your understanding, let's examine a well-written textual resource that provides code in multiple languages.

Detect A Cycle in Directed Graph using DFS - Tutorial

This tutorial from takeuforward provides a complete package: the approach, a visual dry run, code, and complexity analysis.

First, quickly read the Approach section to review the logic of the two-array method. Follow the visual walkthrough under the step-by-step breakdown. It starts with an image labeled Image 1 and progresses through to Image 7, showing how the visited and recursion stack arrays change. Study the Python code provided. Connect the logic in the code to the steps you just visualized. Finally, review the Complexity Analysis. The time complexity is O(V+E), the standard for DFS, and the space complexity is also O(V+E) due to the adjacency list and recursion stack.

Conclusion

In this lesson, we focused on a critical graph algorithm: detecting cycles in a directed graph using DFS. This skill is not only a prerequisite for correctly applying topological sort but is also a frequent interview question in its own right, often disguised as a dependency or scheduling problem.

Key Takeaways:

Back Edges are Key: A cycle in a directed graph is identified by the presence of a "back edge"—an edge from a node to an ancestor in the current DFS path.
Three-State Logic: A simple visited array is not enough. We must distinguish between nodes that are unvisited, visiting (in the current recursion stack), and fully visited.
Implementation Choices: This logic can be implemented with two boolean arrays (visited and recursionStack) or a single integer array representing three "colors" (e.g., WHITE, GRAY, BLACK). Both are equivalent.
The Crucial Backtrack: When a DFS call for a node finishes, it must be removed from the visiting state (i.e., recursionStack[node] = false or color changes from GRAY to BLACK). This is essential for correctly identifying cross-edges versus back edges.

You now have a robust DFS-based method for cycle detection. In our next and final lesson of this module, we will explore an alternative way to detect cycles, this time using Kahn's algorithm (the BFS-based approach).