Cycle Detection

A cycle in a directed graph occurs when there is a path that starts and ends at the exact same node. The Cycle Detection algorithm usually relies on a Depth-First Search (DFS) to traverse the graph and identify if we ever loop back to a node we are currently in the middle of exploring.

         Real-World Application:
        Cycle detection is crucial in modern computing. It is used to find deadlocks in operating
        systems (where processes are endlessly waiting on each other), to resolve circular
        dependencies in software packages, and to ensure spreadsheet formulas don't infinitely
        reference each other.
      

The Algorithm Principle

This implementation uses a recursion stack to track our current path. Nodes can be in one of three states:

Unvisited: The node hasn't been seen yet.
Exploring (Yellow): The node is currently in the recursion stack. We are actively exploring its descendants. If we encounter a node in this state again, we have found a back-edge (a cycle)!
Safe (Green): We have fully explored all paths originating from this node without finding any cycles. It is safe and removed from the recursion stack.

Algorithm Walkthrough

In the script below, we traverse the graph. We flag edges in red the moment a cycle is identified.

def cycle_detection():
    visited = set()
    recursion_stack = set()
    
    # Iterate through all nodes to handle disconnected graphs
    all_nodes = get_all_nodes()
    
    def dfs(u):
        visited.add(u)
        recursion_stack.add(u)
        color_node(u, "#F59E0B", f"Exploring node {u}")
        
        for v in neighbors(u):
            if v not in visited:
                if dfs(v):
                    return True
            elif v in recursion_stack:
                # Cycle detected!
                color_edge(u, v, "#EF4444")
                color_node(u, "#EF4444", f"Cycle detected! Back-edge to {v}")
                return True
        
        # Finished exploring this node
        recursion_stack.remove(u)
        color_node(u, "#10B981", f"Node {u} is safe")
        return False

    for node in all_nodes:
        if node not in visited:
            if dfs(node):
                return # Cycle found, halt execution

    visit(all_nodes[0], "No cycles found in the graph!")

cycle_detection()

Complexity

Metric	Complexity	Explanation
Time Complexity	$O(V + E)$	Where $V$ is the number of vertices and $E$ is the number of edges. In the worst-case scenario, the algorithm visits every vertex once and examines every edge once during the DFS traversal.
Space Complexity	$O(V)$	The space is determined by the maximum depth of the call stack (which can be up to $V$ in a linear graph), as well as the storage needed for the `visited` and `recursion_stack` sets.