Cycle Detection using DFS

Welcome to the next lesson in our graph theory journey. In the previous lesson, you learned how to leverage DFS to find and label all connected components in a graph. This was our first step in using graph traversals to understand a graph's high-level structure. Today, we'll continue this theme by adapting DFS to solve another fundamental problem: detecting cycles.

Your goal for this lesson is to understand and implement algorithms to detect cycles in both undirected and directed graphs. The ability to check for acyclicity is crucial in competitive programming, as many algorithms only work on specific graph structures, such as trees or Directed Acyclic Graphs (DAGs), which we will cover later. You will find that while the core DFS traversal remains the same, the logic for detecting a cycle differs subtly but importantly between undirected and directed graphs.

Cycle Detection in Undirected Graphs

Let's begin with undirected graphs. Imagine you are performing a DFS. You are at a vertex u, and you are about to explore one of its neighbors, v. If you discover that v has already been visited, it implies that there is already a path from the start of your DFS to v. Since there is also a direct edge from u to v, this seems to suggest a cycle.

However, there is a simple catch. In an undirected graph, if you just arrived at u from a parent vertex p, the edge (u, p) exists. When exploring u's neighbors, you will immediately see p, which is of course already visited. This is not a cycle; it's just the edge you used to get to u.

The key insight, therefore, is this: in an undirected graph, if a DFS traversal from vertex u finds an already visited neighbor v that is not the immediate parent of u in the DFS tree, then we have found a cycle. The visited vertex v is an ancestor of u further up the tree, and the edge (u, v) completes the cycle. This special kind of edge is called a back edge.

The following video provides an excellent, step-by-step walkthrough of this exact logic. Pay close attention to how the parent of each node is tracked during the recursive calls.

G-12. Detect a Cycle in an Undirected Graph using DFS | C++ | Java

This video from the "take U forward" channel is specifically designed for competitive programmers. It details the intuition and provides a full dry run of detecting a cycle in an undirected graph using DFS.

Watch these key segments: The core intuition, where the presenter explains why you need to track the parent to avoid false positives. A detailed dry run on an example graph, showing how a cycle is eventually found when the algorithm encounters a visited node that isn't the parent. The pseudo-code explanation, which summarizes the logic before jumping into the full code.

The image below illustrates one such step-by-step detection process. Notice the moment a "back edge" is found, connecting node 3 to the already visited node 0, which is not its immediate parent (node 1 is). This confirms the existence of the cycle 0-1-3-0.

A step-by-step DFS traversal showing how visiting an already-visited node (that is not the immediate parent) detects a cycle through a back edge.

Formalizing with Edge Classification

Since you appreciate the theoretical underpinnings, let's formalize the idea of a back edge. During a DFS traversal, we can classify every edge of the graph based on the state of its endpoint when the edge is first explored. For an undirected graph, it can be proven that only two types of edges arise:

Tree Edges: Edges that lead to an unvisited vertex. These edges form the DFS spanning tree.
Back Edges: Edges (u, v) where v is an ancestor of u in the DFS tree (and v is not the parent of u).

An undirected graph has a cycle if and only if its DFS reveals at least one back edge. Our algorithm is simply a way to find such an edge.

Depth First Search

The cp-algorithms.com article on DFS provides a fantastic, rigorous explanation of edge classification.

Read the section titled "Classification of edges of a graph". Focus on the Theorem and its proof, which formally demonstrates that a DFS on an undirected graph produces only tree edges and back edges. This confirms that our strategy of looking for non-parent, visited nodes is sound.

C++ Implementation for Undirected Graphs

The implementation translates our algorithm directly into C++. The recursive dfs function takes the current vertex and its parent as arguments.

Checking a graph for acyclicity and finding a cycle in O(M)

This article from cp-algorithms.com provides a clean, competitive programming-style implementation.

Examine the C++ code block under the heading "Implementation for undirected graph". Note how the check if(u == par) continue; elegantly handles ignoring the edge back to the parent. The code also demonstrates how to reconstruct the cycle path once it's found, which is a common requirement in problems.

Cycle Detection in Directed Graphs

Now, let's turn our attention to directed graphs. Can we use the same logic? Let's consider a graph with edges 1 -> 2 and 3 -> 2. If we start a DFS from 1, we visit 1 then 2. The traversal from 1 finishes. Later, our main loop starts a new DFS from 3. From 3, we see neighbor 2, which is already visited. Is this a cycle? No. There is no path from 2 back to 3.

The algorithm for undirected graphs fails here. A directed graph has a cycle only if we encounter a node that is currently in our recursion path. In other words, we find a path from a vertex u back to one of its own ancestors v in the current DFS tree. This is also the definition of a back edge in a directed graph.

To implement this, we need to distinguish between three states for each vertex:

Unvisited (White): The node has not been seen at all.
Visiting (Gray): The node is currently in the recursion stack. We have started visiting it, but we have not finished exploring all of its descendants.
Visited (Black): The node and all of its descendants have been fully explored.

The algorithm is as follows: during a DFS, when we are at vertex u, we iterate through its neighbors v. If we encounter a neighbor v that is currently in the "Visiting" (Gray) state, we have found a back edge, and thus a cycle.

This concept is explained very clearly in the following video. It uses two boolean arrays, visited and path_visited, which correspond to our "Black" and "Gray" states respectively.

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

This video, also from "take U forward", masterfully explains why the undirected approach fails for directed graphs and introduces the two-array (or 3-color) solution.

First, watch the demonstration from why the old algorithm fails. This will solidify your understanding of the problem. Next, see the new algorithm introduced from using two visited arrays. The visited array tracks nodes that are "black", while the path_visited array tracks nodes that are "gray". Finally, watch the full walkthrough. It shows precisely how nodes are marked as path_visited upon entering their recursion and unmarked upon exiting, which is the key to the algorithm.

The image below summarizes the core idea. For an undirected graph, a back edge is simple. For a directed graph, the distinction between a back edge (which forms a cycle) and a cross or forward edge (which do not) is crucial. The White-Gray-Black coloring scheme is the standard way to make this distinction.

This diagram contrasts cycle detection in directed and undirected graphs. In directed graphs, a cycle is identified by finding a back edge to a 'gray' (visiting) node, distinguishing it from forward or cross edges.

C++ Implementation for Directed Graphs

The implementation uses an array, often named color, to store the state of each vertex (0 for white, 1 for gray, 2 for black).

Checking a graph for acyclicity and finding a cycle in O(M)

The same cp-algorithms article provides the implementation for the directed case.

Read the short Algorithm section which describes the 3-color scheme. Then, analyze the C++ code for a directed graph. Notice color[v] = 1; when entering the DFS for v, and color[v] = 2; just before exiting. The cycle condition is simply if (color[u] == 1).

Conclusion

You have now added another powerful tool to your graph algorithm toolkit. By making small but critical adjustments to a standard DFS, you can now efficiently determine if a graph contains cycles.

Key Takeaways:

Cycle detection is based on finding back edges during a DFS traversal.
In an undirected graph, a cycle is found when you encounter a visited vertex that is not your immediate parent. This only requires a standard visited array and passing the parent in the DFS call.
In a directed graph, the logic is more strict. A cycle is found only when you encounter a vertex that is currently in the recursion stack (a "gray" node). This requires a 3-state system (white, gray, black), often implemented with a color array or two separate boolean arrays (visited and path_visited).
In both cases, the overall time complexity remains $O (V + E)$ , as the algorithm is a single traversal of the entire graph.

In our upcoming lessons, we will continue to explore properties of graphs using traversals. The next topic will be bipartiteness testing, where we'll determine if a graph's vertices can be divided into two independent sets. This problem provides another classic application of both BFS and DFS.