Detecting Cycles with DFS

1. Cycle Detection in Undirected Graphs

In an undirected graph, edges are two-way. A cycle is a closed loop where you can traverse from a node back to itself without immediately backtracking along the same edge you just used.

The basic idea is to use DFS and keep track of visited nodes. If our DFS traversal encounters a node that has already been visited, we might have found a cycle. However, there's a catch.

Consider a simple graph A -- B. If we start a DFS from A, we visit A, then move to its neighbor B. From B, one of its neighbors is A, which is already visited. Is this a cycle? No, it's just the two-way nature of the edge.

To solve this, our DFS algorithm needs to know not just which nodes are visited, but also how it arrived at the current node. We can do this by keeping track of the parent of each node in the traversal path.

The Rule: During a DFS traversal, if we encounter a visited neighbor that is not the immediate parent of the current node, we have found a cycle.

This video provides an excellent, detailed walkthrough of this exact logic.

The Algorithm in a Nutshell

For each vertex in the graph (to handle disconnected components):

1. If the vertex has not been visited, start a recursive DFS from it. Pass an initial parent value that's impossible (like -1).
2. In the recursive dfs(node, parent) function:
   a. Mark node as visited.
   b. For each neighbor of node:
   i. If neighbor has not been visited, recursively call dfs(neighbor, node). If this recursive call returns true (meaning a cycle was found deeper in the graph), immediately return true.
   ii. Else if the neighbor is not the parent, you've found a cycle! Return true.
3. If the DFS completes for a component without returning true, no cycle was found in that component. If all components are checked and no cycle is found, the graph is acyclic.

Complexity

As this is essentially a standard DFS traversal, the complexity remains the same:

• Time Complexity: $O(V+E)$, where V is the number of vertices and E is the number of edges. We visit each vertex and edge once.
• Space Complexity: $O(V)$ for the visited array and the recursion stack space in the worst case (for a path-like graph).

2. Cycle Detection in Directed Graphs

Now let's turn to directed graphs. Can we use the same parent-checking logic? The answer is no. The problem in directed graphs is different.

Consider a graph where 1 -> 2 and 1 -> 3 -> 2. If we start DFS from 1, we might explore 1 -> 3 -> 2. Now nodes 1, 3, and 2 are marked visited. When we backtrack to 1 and explore the path 1 -> 2, we find that 2 is already visited. But this is not a cycle. It's just two different paths leading to the same node.

The key insight for directed graphs is that a cycle exists if and only if the DFS traversal encounters a "back edge"—an edge that leads from the current node to a node that is an ancestor in the current DFS traversal path.

To implement this, we need to track not just which nodes have been visited globally, but which nodes are currently in the recursion stack.

The Solution: We use two boolean arrays:

1. visited[]: Tracks nodes that have been visited at any point. This prevents redundant processing of the same node across different DFS paths.
2. pathVisited[] (also called onStack[] or recursionStack[]): Tracks nodes that are currently in the recursion path of the active DFS traversal.

The Rule: During a DFS, if we encounter a neighbor that is already in the pathVisited[] array, we have found a cycle.

This video first explains why the undirected method fails and then walks through the two-array solution.

The Algorithm in a Nutshell

1. Initialize a visited array and a pathVisited array to all false.
2. For each vertex v in the graph:
   a. If v is not visited, call dfs_check(v).
3. In the recursive dfs_check(node) function:
   a. Mark node as true in both visited and pathVisited.
   b. For each neighbor of node:
   i. If neighbor is not visited, call dfs_check(neighbor). If it returns true, a cycle was found, so return true immediately.
   ii. Else if neighbor is already marked true in pathVisited, we've hit an ancestor in the current path. Cycle detected! Return true.
   c. Before the function returns, un-mark node in pathVisited (set it to false). This is the backtracking step, signifying that node is no longer in the current recursion path.
   d. Return false (no cycle found from this node).

For a good textual summary and Java code examples, this article is a helpful supplement.

Conclusion

You have now learned how to adapt DFS to solve the critical problem of cycle detection. The key is understanding that the definition of a "back edge" differs between undirected and directed graphs, requiring two distinct approaches.

Key Takeaways:

• Cycle detection is a powerful application of DFS.
• For undirected graphs, a cycle is found when DFS hits a visited node that is not its immediate parent. The algorithm is a DFS that passes a parent reference.
• For directed graphs, a cycle is found when DFS hits a node that is currently in the recursion stack. The algorithm uses two arrays: visited and pathVisited (or onStack).
• In both cases, the time complexity is $O(V+E)$ because the underlying algorithm is still DFS.

Preview of the Next Lesson:
Our work with directed graphs and cycles leads directly to our next topic: Topological Sorting. This algorithm orders the vertices of a Directed Acyclic Graph (DAG) such that for every directed edge from vertex u to vertex v, u comes before v in the ordering. As the name implies, it only works on graphs with no cycles. You've just learned how to verify that prerequisite