Cycle Detection - Learning Module

Loading content...

0/276

Cycle Detection in Undirected Graphs

The Loop That Shouldn't Exist

Imagine you're building a dependency management system for a large software project. Package A depends on B, B depends on C, and C depends on... A. You've just discovered a circular dependency—a cycle that makes your entire build system grind to a halt. No package can be installed first because each one waits for another.

This scenario illustrates one of the most important graph problems in computer science: cycle detection. A cycle in a graph is a path that starts and ends at the same vertex, passing through at least one edge. Detecting cycles is essential for:

Validating that dependencies can be resolved
Detecting deadlocks in concurrent systems
Ensuring tree structures remain acyclic
Finding infinite loops in state machines
Verifying database referential integrity

What You Will Learn

By the end of this page, you will master cycle detection in undirected graphs using both DFS and Union-Find approaches. You'll understand the fundamental difference between back edges and cross edges, and be able to implement production-quality cycle detection with precise parent tracking.

Understanding Cycles in Undirected Graphs

In an undirected graph, a cycle exists when there is a path from a vertex back to itself that uses at least three distinct vertices. This constraint is crucial—without it, every edge in an undirected graph would trivially form a "cycle" by going back and forth.

Formal Definition:

A cycle in an undirected graph G = (V, E) is a sequence of vertices v₀, v₁, v₂, ..., vₖ where:

k ≥ 2 (at least 3 vertices in the cycle)
v₀ = vₖ (the path returns to its starting vertex)
All edges (vᵢ, vᵢ₊₁) exist in E
All vertices v₀, v₁, ..., vₖ₋₁ are distinct

The minimum cycle length is 3 (a triangle). A graph with no cycles is called a forest, and a connected forest is a tree.

The Parent Edge Trap

In undirected graphs, edges are bidirectional. When traversing from vertex A to B, you can immediately go back from B to A. This is NOT a cycle—it's just traversing the same edge twice. The key insight for cycle detection is distinguishing between going back on the edge you came from (the parent edge) versus finding an alternative path back (a true cycle).

Edge Classification in Undirected Graphs:

During a DFS traversal of an undirected graph, edges fall into two categories:

Tree Edges: Edges that are part of the DFS tree—they lead to unvisited vertices
Back Edges: Edges that connect a vertex to an already-visited ancestor in the DFS tree

The critical insight is: A cycle exists if and only if we encounter a back edge. When we find an edge to an already-visited vertex that is NOT our immediate parent, we've discovered an alternative path back—a cycle.

Graph Properties and Cycle Existence
Property	Cycle Exists?	Reasoning
V vertices, V-1 edges, connected	No	This is exactly a tree—minimum edges for connectivity
V vertices, V edges, connected	Yes	One extra edge beyond tree creates exactly one cycle
V vertices, < V-1 edges	No	Graph is disconnected (forest), no component has cycles
Complete graph (all edges)	Yes	Contains many cycles (triangles, squares, etc.)

DFS Approach: Tracking Visited Vertices and Parents

The DFS-based approach for cycle detection in undirected graphs works by maintaining two pieces of information during traversal:

visited[]: A boolean array tracking which vertices have been explored
parent: The vertex from which we arrived at the current vertex

The Algorithm:

Starting from any unvisited vertex, perform DFS. For each vertex v:

Mark v as visited
For each neighbor u of v:
- If u is not visited, recursively explore u with parent = v
- If u IS visited AND u is NOT the parent of v, we've found a cycle

The parent check is essential because in an undirected graph, every edge appears twice in the adjacency list. When we go from v to u, the edge (u, v) will appear when exploring u's neighbors. We must NOT report this as a cycle.

cycle_detection_undirected.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
from collections import defaultdict
from typing import List, Optional, Tuple
 
class UndirectedGraph:
    """
    Undirected graph with cycle detection capability.
    Uses adjacency list representation.
    """
    
    def __init__(self, vertices: int):
        self.V = vertices
        self.adj = defaultdict(list)
    
    def add_edge(self, u: int, v: int) -> None:
        """Add undirected edge between u and v."""
        self.adj[u].append(v)
        self.adj[v].append(u)
    
    def has_cycle(self) -> bool:
        """
        Detect if the graph contains any cycle.
        
        Returns:
            True if a cycle exists, False otherwise.
        
        Time Complexity: O(V + E) - each vertex and edge visited once
        Space Complexity: O(V) - for visited array and recursion stack
        """
        visited = [False] * self.V
        
        # Check all components (graph may be disconnected)
        for vertex in range(self.V):
            if not visited[vertex]:
                if self._dfs_has_cycle(vertex, visited, parent=-1):
                    return True
        return False
    
    def _dfs_has_cycle(
        self, 
        vertex: int, 
        visited: List[bool], 
        parent: int
    ) -> bool:
        """
        DFS helper that detects cycle from given vertex.
        
        Args:
            vertex: Current vertex being explored
            visited: Array tracking visited vertices
            parent: The vertex from which we arrived at current vertex
        
        Returns:
            True if a cycle is detected, False otherwise.
        """
        visited[vertex] = True
        
        for neighbor in self.adj[vertex]:
            if not visited[neighbor]:
                # Explore unvisited neighbor
                if self._dfs_has_cycle(neighbor, visited, parent=vertex):
                    return True
            elif neighbor != parent:
                # Found visited vertex that isn't our parent - CYCLE!
                return True
        
        return False
    
    def find_cycle(self) -> Optional[List[int]]:
        """
        Find and return one cycle if it exists.
        
        Returns:
            List of vertices forming a cycle, or None if no cycle exists.
        """
        visited = [False] * self.V
        parent = [-1] * self.V
        
        for start in range(self.V):
            if not visited[start]:
                cycle = self._dfs_find_cycle(start, visited, parent)
                if cycle:
                    return cycle
        return None
    
    def _dfs_find_cycle(
        self,
        vertex: int,
        visited: List[bool],
        parent: List[int]
    ) -> Optional[List[int]]:
        """
        DFS helper that finds and reconstructs a cycle.
        """
        visited[vertex] = True
        
        for neighbor in self.adj[vertex]:
            if not visited[neighbor]:
                parent[neighbor] = vertex
                result = self._dfs_find_cycle(neighbor, visited, parent)
                if result:
                    return result
            elif neighbor != parent[vertex]:
                # Cycle found! Reconstruct it
                cycle = [vertex]
                current = vertex
                while current != neighbor:
                    current = parent[current]
                    cycle.append(current)
                cycle.append(vertex)  # Complete the cycle
                return cycle[::-1]  # Reverse to get correct order
        
        return None
 
 
# Example usage demonstrating cycle detection
if __name__ == "__main__":
    # Graph with a cycle: 0-1-2-0 (triangle)
    g1 = UndirectedGraph(5)
    g1.add_edge(0, 1)
    g1.add_edge(1, 2)
    g1.add_edge(2, 0)  # Creates cycle
    g1.add_edge(2, 3)
    g1.add_edge(3, 4)
    
    print(f"Graph 1 has cycle: {g1.has_cycle()}")  # True
    print(f"Cycle found: {g1.find_cycle()}")  # [0, 1, 2, 0]
    
    # Tree (no cycle)
    g2 = UndirectedGraph(4)
    g2.add_edge(0, 1)
    g2.add_edge(0, 2)
    g2.add_edge(1, 3)
    
    print(f"Graph 2 has cycle: {g2.has_cycle()}")  # False
    print(f"Cycle found: {g2.find_cycle()}")  # None

Why -1 for Initial Parent?

We use -1 (or any invalid vertex ID) as the parent for the starting vertex because it has no parent—we didn't arrive there from anywhere. This ensures the first vertex's neighbors are all checked properly without false cycle detection.

Visual Trace: Step-by-Step Cycle Detection

Let's trace through the algorithm on a concrete example to build intuition. Consider this undirected graph with 5 vertices and a cycle:

Graph Structure:

Edges: (0,1), (1,2), (2,3), (3,1), (3,4)
The cycle is: 1 → 2 → 3 → 1

We'll trace the DFS starting from vertex 0, tracking visited status and parent relationships at each step.

DFS Trace for Cycle Detection
Step	Current	Parent	Action	Visited Array	Result
1	0	-1	Start DFS from 0	[T,F,F,F,F]	Continue
2	1	0	Visit neighbor 1 (unvisited)	[T,T,F,F,F]	Continue
3	2	1	Visit neighbor 2 (unvisited)	[T,T,T,F,F]	Continue
4	3	2	Visit neighbor 3 (unvisited)	[T,T,T,T,F]	Continue
5	3→1	2	Check neighbor 1: visited AND ≠ parent	[T,T,T,T,F]	CYCLE FOUND!

Critical Observation at Step 5:

When at vertex 3 (with parent = 2), we examine its neighbors: 2 and 1.

Neighbor 2: Visited but parent = 2, so skip (this is the edge we came from)
Neighbor 1: Visited AND 1 ≠ 2 (not our parent), so CYCLE DETECTED

The cycle exists because we found a path from 3 back to 1 without using the edge we arrived on. This forms the cycle 1 → 2 → 3 → 1.

The Back Edge Perspective

In graph theory terms, when we detect that neighbor 1 is visited and isn't our parent, we've found a "back edge"—an edge that connects to an ancestor in the DFS tree. Every back edge in an undirected graph indicates a cycle, and every cycle contains at least one back edge.

Union-Find Approach: An Alternative Perspective

The Union-Find (Disjoint Set Union) data structure provides an elegant alternative for cycle detection in undirected graphs. Instead of traversing the graph, we process edges one by one and check if adding an edge would create a cycle.

The Insight:

A cycle is formed when we add an edge between two vertices that are already in the same connected component. If vertices u and v are already connected via some path, adding edge (u, v) creates a second path between them—thus forming a cycle.

Algorithm:

Initialize each vertex as its own component
For each edge (u, v) in the graph:
- Find the root/representative of u's component
- Find the root/representative of v's component
- If they have the same root → CYCLE (already connected)
- Otherwise, union the two components

union_find_cycle.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
class UnionFind:
    """
    Disjoint Set Union (Union-Find) with path compression 
    and union by rank for near-constant time operations.
    """
    
    def __init__(self, n: int):
        self.parent = list(range(n))  # Each element is its own parent
        self.rank = [0] * n           # Rank for union by rank optimization
    
    def find(self, x: int) -> int:
        """
        Find the root/representative of x's component.
        Uses path compression for O(α(n)) amortized time.
        """
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]
    
    def union(self, x: int, y: int) -> bool:
        """
        Unite the components containing x and y.
        
        Returns:
            True if union was performed (x and y were in different components)
            False if x and y were already in the same component (cycle!)
        """
        root_x = self.find(x)
        root_y = self.find(y)
        
        if root_x == root_y:
            return False  # Already in same component - adding edge creates cycle
        
        # Union by rank: attach smaller tree under larger tree
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        
        return True
 
 
def has_cycle_union_find(vertices: int, edges: list[tuple[int, int]]) -> bool:
    """
    Detect cycle using Union-Find approach.
    
    Args:
        vertices: Number of vertices in the graph
        edges: List of (u, v) edges
    
    Returns:
        True if the graph contains a cycle
    
    Time Complexity: O(E × α(V)) ≈ O(E) for practical purposes
    Space Complexity: O(V) for Union-Find data structure
    """
    uf = UnionFind(vertices)
    
    for u, v in edges:
        if not uf.union(u, v):
            return True  # Edge connects vertices already in same component
    
    return False
 
 
def find_cycle_union_find(
    vertices: int, 
    edges: list[tuple[int, int]]
) -> tuple[int, int] | None:
    """
    Find the edge that completes a cycle.
    
    Returns:
        The edge (u, v) that creates the cycle, or None if no cycle.
    """
    uf = UnionFind(vertices)
    
    for u, v in edges:
        if not uf.union(u, v):
            return (u, v)  # This edge creates the cycle
    
    return None
 
 
# Example usage
if __name__ == "__main__":
    # Edges that form a triangle cycle
    edges1 = [(0, 1), (1, 2), (2, 0)]
    print(f"Edges {edges1} has cycle: {has_cycle_union_find(3, edges1)}")  # True
    print(f"Cycle-creating edge: {find_cycle_union_find(3, edges1)}")  # (2, 0)
    
    # Edges forming a tree (no cycle)
    edges2 = [(0, 1), (0, 2), (1, 3)]
    print(f"Edges {edges2} has cycle: {has_cycle_union_find(4, edges2)}")  # False
    
    # More complex case
    edges3 = [(0, 1), (1, 2), (2, 3), (3, 1)]  # Cycle 1-2-3
    print(f"Edges {edges3} has cycle: {has_cycle_union_find(4, edges3)}")  # True
    print(f"Cycle-creating edge: {find_cycle_union_find(4, edges3)}")  # (3, 1)

Union-Find Advantages

•Edge-oriented: Processes edges directly without building adjacency list
•Identifies culprit edge: Reports which edge creates the cycle
•Near-linear time: O(E × α(V)) where α is inverse Ackermann (effectively constant)
•Incremental: Can add edges one at a time and check after each

Union-Find Limitations

•Cycle reconstruction harder: Doesn't directly give the full cycle path
•Only for undirected: Cannot detect directed cycles (different semantics)
•Order dependent: Different edge orderings detect cycle at different edges
•Extra space: Requires parent and rank arrays

Complexity Analysis and Comparison

Both approaches are efficient, but they have different characteristics that make them suitable for different scenarios.

DFS vs Union-Find for Cycle Detection
Aspect	DFS Approach	Union-Find Approach
Time Complexity	O(V + E)	O(E × α(V)) ≈ O(E)
Space Complexity	O(V) + recursion stack	O(V)
Returns full cycle	Yes (with modification)	No (only edge)
Works incrementally	No (needs full graph)	Yes
Implementation complexity	Simpler	Requires Union-Find DS
Works for directed graphs	Yes (with modification)	No

Choosing the Right Approach

Use DFS when you need the actual cycle path, when working with directed graphs, or when you already have the graph built. Use Union-Find when you're building the graph incrementally and want to detect the moment a cycle is created, or when you need to process edges in a streaming fashion.

Practical Considerations:

Memory: For very large sparse graphs, DFS with recursion might cause stack overflow. In such cases, either use iterative DFS with explicit stack or Union-Find.

Disconnected Graphs: Both approaches handle disconnected graphs correctly. DFS iterates over all vertices to start from unvisited ones; Union-Find naturally processes all edges regardless of connectivity.

Multiple Cycles: Both approaches detect if any cycle exists but stop at the first one found. To find all cycles, more sophisticated algorithms are needed (though this is often computationally expensive).

BFS-Based Cycle Detection

While DFS is the most common approach, BFS can also detect cycles in undirected graphs using the same parent-tracking principle. The logic is identical: if we encounter a visited vertex that is not our parent, a cycle exists.

Why consider BFS?

Avoids deep recursion: No risk of stack overflow for deep graphs
Level information: BFS naturally provides distance from source
Shortest cycle path: When a cycle is detected via BFS, the path found is one of the shortest (in terms of edges)

bfs_cycle_detection.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
from collections import deque
 
def has_cycle_bfs(vertices: int, adj: dict[int, list[int]]) -> bool:
    """
    Detect cycle in undirected graph using BFS.
    
    Same logic as DFS: if we find a visited vertex that isn't 
    our parent, a cycle exists.
    
    Time: O(V + E), Space: O(V)
    """
    visited = [False] * vertices
    parent = [-1] * vertices
    
    for start in range(vertices):
        if visited[start]:
            continue
            
        queue = deque([start])
        visited[start] = True
        
        while queue:
            vertex = queue.popleft()
            
            for neighbor in adj.get(vertex, []):
                if not visited[neighbor]:
                    visited[neighbor] = True
                    parent[neighbor] = vertex
                    queue.append(neighbor)
                elif neighbor != parent[vertex]:
                    # Visited neighbor that isn't parent - CYCLE!
                    return True
    
    return False
 
 
def find_shortest_cycle_bfs(
    vertices: int, 
    adj: dict[int, list[int]]
) -> list[int] | None:
    """
    Find the shortest cycle in the graph using BFS.
    
    BFS guarantees we find a cycle using the minimum number of edges
    from any given starting point.
    """
    shortest_cycle = None
    
    # Try starting from each vertex
    for source in range(vertices):
        visited = [False] * vertices
        parent = [-1] * vertices
        distance = [-1] * vertices
        
        queue = deque([source])
        visited[source] = True
        distance[source] = 0
        
        while queue:
            vertex = queue.popleft()
            
            for neighbor in adj.get(vertex, []):
                if not visited[neighbor]:
                    visited[neighbor] = True
                    parent[neighbor] = vertex
                    distance[neighbor] = distance[vertex] + 1
                    queue.append(neighbor)
                elif neighbor != parent[vertex]:
                    # Cycle found! Reconstruct it
                    cycle_length = distance[vertex] + distance[neighbor] + 1
                    
                    # Reconstruct cycle path
                    cycle = []
                    
                    # Path from vertex back to common ancestor
                    p1, p2 = vertex, neighbor
                    path1, path2 = [p1], [p2]
                    
                    while p1 != source:
                        p1 = parent[p1]
                        path1.append(p1)
                    while p2 != source:
                        p2 = parent[p2]
                        path2.append(p2)
                    
                    # Find where paths diverge from source
                    path1.reverse()
                    path2.reverse()
                    
                    # Build cycle: path to vertex + edge to neighbor + path back
                    while (path1 and path2 and 
                           len(path1) > 1 and len(path2) > 1 and
                           path1[1] == path2[1]):
                        path1.pop(0)
                        path2.pop(0)
                    
                    cycle = path1 + path2[::-1][1:]
                    
                    if shortest_cycle is None or len(cycle) < len(shortest_cycle):
                        shortest_cycle = cycle
                        break
            
            if shortest_cycle and len(shortest_cycle) == 3:
                break  # Can't get shorter than a triangle
    
    return shortest_cycle
 
 
# Example
adj = {
    0: [1, 4],
    1: [0, 2, 3],
    2: [1, 3],
    3: [1, 2, 4],
    4: [0, 3]
}
 
print(f"Has cycle: {has_cycle_bfs(5, adj)}")  # True

Edge Cases and Robustness

Production-quality cycle detection must handle various edge cases gracefully. Let's examine the scenarios that can trip up naive implementations:

Critical Edge Cases

•Empty Graph: Zero vertices or zero edges should return false (no cycle possible)
•Single Vertex: One vertex with no edges—no cycle
•Self-Loop: Edge from vertex to itself (v, v)—this IS a cycle! Neither DFS parent-check nor Union-Find naturally handle this; add explicit check
•Multi-Edges: Multiple edges between same pair (multigraph)—traditional adjacency list DFS may falsely detect cycle; need edge-based parent tracking
•Disconnected Components: Graph has multiple separate parts—must check all components
•Very Deep Graphs: Long chains may cause stack overflow—use iterative DFS or BFS

robust_cycle_detection.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
def has_cycle_robust(
    vertices: int,
    edges: list[tuple[int, int]]
) -> bool:
    """
    Robust cycle detection handling all edge cases.
    """
    if vertices == 0:
        return False
    
    # Check for self-loops explicitly
    for u, v in edges:
        if u == v:
            return True  # Self-loop is a cycle
    
    # Build adjacency list with edge indices for multi-edge handling
    adj: dict[int, list[tuple[int, int]]] = {i: [] for i in range(vertices)}
    for idx, (u, v) in enumerate(edges):
        adj[u].append((v, idx))
        adj[v].append((u, idx))
    
    visited = [False] * vertices
    
    def dfs(vertex: int, parent_edge: int) -> bool:
        """
        DFS with edge-based parent tracking for multi-edge correctness.
        
        Instead of tracking parent vertex, we track the edge index
        we used to arrive. This prevents false positives when multiple
        edges exist between the same pair.
        """
        visited[vertex] = True
        
        for neighbor, edge_idx in adj[vertex]:
            if not visited[neighbor]:
                if dfs(neighbor, edge_idx):
                    return True
            elif edge_idx != parent_edge:
                # Found visited vertex via different edge - CYCLE!
                return True
        
        return False
    
    # Check all components with iterative wrapper to avoid stack overflow
    for start in range(vertices):
        if not visited[start]:
            if dfs(start, -1):
                return True
    
    return False
 
 
# Test edge cases
print(has_cycle_robust(0, []))  # False - empty graph
print(has_cycle_robust(1, []))  # False - single vertex
print(has_cycle_robust(1, [(0, 0)]))  # True - self-loop!
print(has_cycle_robust(2, [(0, 1), (0, 1)]))  # True - multi-edge forms cycle?
 
# Note: For multi-edges between same pair, interpretation varies.
# Some definitions consider parallel edges as NOT forming a cycle
# (since they don't form a simple cycle with 3+ distinct vertices).
# Adjust based on your problem's requirements.

Multi-Edge Ambiguity

Whether parallel edges (multiple edges between the same vertex pair) constitute a cycle is definitionally ambiguous. In simple graphs, parallel edges aren't allowed. In multigraphs, you may or may not want to consider them as cycles. Clarify requirements before implementing.

Summary: Cycle Detection in Undirected Graphs

We've covered the complete landscape of cycle detection in undirected graphs. Let's consolidate the key insights:

Key Takeaways

•A cycle exists when we find a back edge—an edge to an already-visited vertex that isn't our immediate parent
•DFS with parent tracking is the standard approach: O(V + E) time, O(V) space
•Union-Find offers an edge-centric view: O(E × α(V)) time, naturally reports the cycle-creating edge
•BFS works equally well and avoids recursion depth issues
•Self-loops require special handling—they're cycles but don't fit the parent-checking paradigm
•Disconnected graphs need complete coverage—iterate through all vertices as potential starting points

Coming Up Next:

In the next page, we'll tackle cycle detection in directed graphs—a fundamentally different problem that requires more sophisticated state tracking. The presence of directed edges means we must distinguish between edges to ancestors in the current path versus edges to previously completed paths.

Page Complete

You now have a comprehensive understanding of cycle detection in undirected graphs. You can implement both DFS and Union-Find approaches, handle edge cases robustly, and choose the right algorithm based on your specific requirements. Next, we'll extend these concepts to the more challenging domain of directed graphs.