Cycle Detection in Graphs using DFS

Recap: The Essence of DFS

As a quick refresher, DFS explores a graph by going as deep as possible down one path before backtracking. This "deep-dive" nature is exactly what we need for cycle detection. A cycle occurs when our deep exploration leads us back to a node we've already encountered in our current path.

Part 1: Cycle Detection in Undirected Graphs

In an undirected graph, if an edge exists between u and v, we can travel from u to v and also from v to u.

The simplest idea for cycle detection is: while traversing, if we encounter a node that has already been visited, we have found a cycle. But there's a catch with undirected graphs.

Consider an edge A -- B.

1. We start DFS from A.
2. We visit A and move to its neighbor B.
3. From B, one of its neighbors is A. Since A is already visited, does this mean we have a cycle? No, this is just the edge we used to get to B.

To solve this, we need to distinguish between finding a true cycle and simply moving back to the immediate node we came from. The solution is to keep track of the parent of the current node in the DFS traversal. A cycle is detected if we encounter a visited node that is not the parent of the current node.

The Algorithm

For each vertex u:

1. Mark u as visited.
2. For each neighbor v of u:
   • If v is not visited, recursively call DFS on v, with u as its parent. If the recursive call returns true (finds a cycle), then propagate true up.
   • If v is visited AND v is not the parent of u, we have found a back edge, which means there is a cycle. Return true.
3. If the loop finishes without finding a cycle, return false.

To see this logic in action, let's watch a detailed walkthrough.

Python Implementation

Here is a Python implementation based on the logic we've discussed. We use an adjacency list to represent the graph, which is standard in competitive programming.

from collections import defaultdict

def has_cycle_undirected_util(u, parent, visited, adj):
    """A recursive DFS utility to detect cycles."""
    visited.add(u)

    for v in adj[u]:
        if v not in visited:
            # If a cycle is found in the subtree, propagate it up.
            if has_cycle_undirected_util(v, u, visited, adj):
                return True
        # If v is visited and is not the parent of u, we found a back edge.
        elif v != parent:
            return True
            
    return False

def has_cycle_undirected(num_nodes, edges):
    """Checks for a cycle in an undirected graph."""
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    
    visited = set()
    
    # This loop handles disconnected components in the graph.
    for i in range(num_nodes):
        if i not in visited:
            # Call DFS. The parent of the starting node is -1 (a dummy value).
            if has_cycle_undirected_util(i, -1, visited, adj):
                return True
                
    return False

# --- Example Usage ---
num_nodes_1 = 5
edges_1 = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 1)] # Cycle: 1-2-3-4-1
print(f"Graph 1 has cycle: {has_cycle_undirected(num_nodes_1, edges_1)}") # Expected: True

num_nodes_2 = 4
edges_2 = [(0, 1), (1, 2), (2, 3)] # No cycle
print(f"Graph 2 has cycle: {has_cycle_undirected(num_nodes_2, edges_2)}") # Expected: False

Part 2: Cycle Detection in Directed Graphs

The "parent" trick does not work for directed graphs. Consider the path A -> B and C -> B. If we traverse A -> B first, B becomes visited. Later, if we start a new traversal from C and reach B, B is visited, and its parent in this new path is C, not A. Our previous logic would incorrectly flag a cycle.

The key difference in a directed graph is that a cycle only exists if we follow the direction of the edges and end up back where we started.

To detect this, we need to know if we've encountered a node that is currently part of our active exploration path (i.e., it's an ancestor in the current recursion stack).

The Three-State Approach

We can track the state of each node using three categories:

1. UNVISITED: The node has not been seen yet.
2. VISITING: The node is currently in our recursion stack. We have started exploring from it, but we haven't finished exploring all its descendants.
3. VISITED: We have finished exploring this node and all its descendants.

A cycle is detected if, during our DFS, we encounter a neighbor that is in the VISITING state.

Algorithm Walkthrough

A classic competitive programming problem that boils down to detecting a cycle in a directed graph is "Course Schedule" (LeetCode 207). To take a set of courses, you must satisfy all prerequisites. A cyclic dependency (e.g., Course A requires B, and B requires A) makes it impossible to finish.

The following video explains this problem and demonstrates the three-state DFS approach.

Python Implementation

We can implement the three states using an array, say states, where 0 = unvisited, 1 = visiting, and 2 = visited.

from collections import defaultdict

# States for directed graph cycle detection
UNVISITED = 0
VISITING = 1
VISITED = 2

def has_cycle_directed_util(u, states, adj):
    """A recursive DFS utility for directed graphs."""
    states[u] = VISITING

    for v in adj[u]:
        if states[v] == UNVISITED:
            if has_cycle_directed_util(v, states, adj):
                return True
        # If we encounter a node that is currently in our recursion stack.
        elif states[v] == VISITING:
            return True

    # Mark as fully explored once all neighbors are done.
    states[u] = VISITED
    return False

def has_cycle_directed(num_nodes, edges):
    """Checks for a cycle in a directed graph."""
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
    
    states = [UNVISITED] * num_nodes
    
    for i in range(num_nodes):
        if states[i] == UNVISITED:
            if has_cycle_directed_util(i, states, adj):
                return True
                
    return False

# --- Example Usage ---
num_nodes_3 = 4
edges_3 = [(0, 1), (1, 2), (2, 0), (2, 3)] # Cycle: 0->1->2->0
print(f"\nGraph 3 has cycle: {has_cycle_directed(num_nodes_3, edges_3)}") # Expected: True

num_nodes_4 = 4
edges_4 = [(0, 1), (0, 2), (1, 3), (2, 3)] # No cycle (DAG)
print(f"Graph 4 has cycle: {has_cycle_directed(num_nodes_4, edges_4)}") # Expected: False

Complexity Analysis

For both the undirected and directed versions of the DFS-based cycle detection:

• Time Complexity: $O(V+E)$, where $V$ is the number of vertices and $E$ is the number of edges. Each vertex is visited once, and all its outgoing edges are checked once.
• Space Complexity: $O(V)$. This is for the visited set/states array and for the recursion call stack, which in the worst case (a long chain of nodes) can go as deep as $V$.

Conclusion

You've now mastered a critical graph algorithm: using Depth-First Search to detect cycles. This skill is invaluable for solving a wide range of problems in competitive programming and software engineering.

Key Takeaways:

• Cycle detection builds directly on the DFS traversal pattern.
• For undirected graphs, the key is to track the parent node to avoid false positives from immediate back edges. A cycle exists if you find a visited neighbor that is not your parent.
• For directed graphs, the parent method is insufficient. The correct approach is to use a three-state system (unvisited, visiting, visited) to track nodes in the current recursion path. A cycle exists if you find a neighbor that is currently in the visiting state.

Up Next:
We will continue building on our graph traversal skills. In the next lesson, we'll see how to use DFS or BFS to another common problem: finding connected components in an undirected graph. This is useful for determining if a graph is a single entity or composed of several disjoint subgraphs.