Data Structures & AlgorithmsGraph Algorithms

Cycle Detection

LevelIntermediate

Duration90 mins

TopicGraph Algorithms

2 / 4

Cycle Detection in Directed Graphs

When Direction Changes Everything

Consider a build system compiling your code. Module A imports from B, B imports from C. Each import is directional —A depends on B, not vice versa. Now imagine C also imports from A. This creates a directed cycle : A \to B \to C \to A. No module can be compiled first because each waits for another in an endless loop. This scenario illustrates why cycle detection in directed graphs is fundamentally different from undirected graphs. In undirected graphs, if you can get from A to B, you can always get from B to A. In directed graphs, reachability is asymmetric—paths have direction, and this changes everything about cycle detection.

What You Will Learn

By the end of this page, you will master the three-color DFS algorithm for directed cycle detection, understand why the undirected approach fails for directed graphs, and be able to implement production-quality cycle detection with cycle reconstruction capabilities.

Why the Undirected Approach Fails for Directed Graphs

Let's first understand why we can't simply use the parent-tracking approach from undirected graphs. The Core Problem: In undirected graphs, when we visit a vertex that's already visited AND it's not our parent, we've found an alternative path back—a cycle. But in directed graphs, finding a visited vertex doesn't necessarily mean we've found a cycle. Consider this directed graph: 0 \to 1 \to 3 ↓ ↑ 2 ──────┘ Vertex 3 is reachable from 0 via two paths: 0\to1\to3 and 0\to2\to3. When DFS explores 0\to1\to3 first, vertex 3 gets marked visited. Then when exploring 0\to2, we find edge 2\to3 leading to already-visited 3. Is this a cycle? No! There's no way to get back from 3 to any vertex in our current path. We've just found a cross edge —an edge to a vertex that was completed in a different branch of the DFS tree.

The Fundamental Distinction

In directed graphs, we must distinguish between: (1) edges to vertices currently in our recursion stack (BACK EDGES \to cycles), and (2) edges to vertices already completely explored in a different path (CROSS/FORWARD EDGES \to no cycle). A simple visited/unvisited distinction cannot make this differentiation.

Edge Classification in Directed Graphs: During DFS of a directed graph, edges are classified into four types: Tree Edges : Lead to unvisited vertices (part of DFS tree) Back Edges : Lead to an ancestor in the current DFS path \to INDICATES CYCLE Forward Edges : Lead to a descendant that was already visited Cross Edges : Lead to a vertex visited in a different subtree Only back edges create cycles. Our algorithm must specifically detect back edges, which means tracking not just "visited" but "currently in the active DFS path."

Comparing Undirected vs Directed Cycle Detection
Aspect	Undirected Graph	Directed Graph
What indicates cycle?	Any edge to visited non-parent	Only edge to ancestor in current path
Edge types	Tree edges, Back edges only	Tree, Back, Forward, Cross edges
Sufficient tracking	visited[] array	Need recursion stack state
Parent tracking	Required to avoid false positives	Not needed (edges are one-way)
Cross edges	Don't exist (would be back edges)	Exist and must not trigger false positive

The Three-Color DFS Algorithm

The standard algorithm for detecting cycles in directed graphs uses a three-color marking scheme (or equivalently, tracking an explicit recursion stack). Each vertex can be in one of three states: WHITE (Unvisited) : The vertex has not yet been discovered. GRAY (In Progress) : The vertex is currently being explored—it's in our active DFS path. We've started exploring it but haven't finished (still have unvisited neighbors). BLACK (Completed) : The vertex and ALL its descendants have been fully explored. We've finished with it completely. The Key Insight: A cycle exists if and only if we find an edge from a GRAY vertex to another GRAY vertex. This is a back edge—an edge from a vertex in the current path back to an ancestor in that same path.

directed_cycle_detection.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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
from collections import defaultdict
from enum import Enum
from typing import Optional
 
class Color(Enum):
    """
    Three-color states for directed graph DFS.
    """
    WHITE = 0  # Unvisited
    GRAY = 1   # Currently in DFS path (in progress)
    BLACK = 2  # Completely processed
 
 
class DirectedGraph:
    """
    Directed graph with cycle detection using three-color DFS.
    """
    
    def __init__(self, vertices: int):
        self.V = vertices
        self.adj: dict[int, list[int]] = defaultdict(list)
    
    def add_edge(self, u: int, v: int) -> None:
        """Add directed edge from u to v."""
        self.adj[u].append(v)
    
    def has_cycle(self) -> bool:
        """
        Detect if the directed graph contains a cycle.
        
        Uses three-color DFS:
        - WHITE: unvisited
        - GRAY: currently in DFS stack (being processed)
        - BLACK: completely finished
        
        A cycle exists iff we find a GRAY → GRAY edge (back edge).
        
        Time Complexity: O(V + E)
        Space Complexity: O(V)
        """
        color = [Color.WHITE] * self.V
        
        for vertex in range(self.V):
            if color[vertex] == Color.WHITE:
                if self._dfs_has_cycle(vertex, color):
                    return True
        return False
    
    def _dfs_has_cycle(self, vertex: int, color: list[Color]) -> bool:
        """
        DFS helper for cycle detection.
        
        Returns True if cycle is found starting from vertex.
        """
        # Mark as gray (in progress / in current DFS path)
        color[vertex] = Color.GRAY
        
        for neighbor in self.adj[vertex]:
            if color[neighbor] == Color.GRAY:
                # Found edge to vertex in current path - CYCLE!
                return True
            elif color[neighbor] == Color.WHITE:
                # Explore unvisited neighbor
                if self._dfs_has_cycle(neighbor, color):
                    return True
            # If BLACK, neighbor was fully processed in different path
            # This is a cross edge or forward edge - NOT a cycle
        
        # Mark as black (completely processed)
        color[vertex] = Color.BLACK
        return False
    
    def find_cycle(self) -> Optional[list[int]]:
        """
        Find and return a cycle if one exists.
        
        Returns:
            List of vertices forming the cycle, or None if no cycle.
        """
        color = [Color.WHITE] * self.V
        parent = [-1] * self.V
        
        for vertex in range(self.V):
            if color[vertex] == Color.WHITE:
                cycle = self._dfs_find_cycle(vertex, color, parent)
                if cycle:
                    return cycle
        return None
    
    def _dfs_find_cycle(
        self,
        vertex: int,
        color: list[Color],
        parent: list[int]
    ) -> Optional[list[int]]:
        """
        DFS helper that returns the cycle path when found.
        """
        color[vertex] = Color.GRAY
        
        for neighbor in self.adj[vertex]:
            if color[neighbor] == Color.GRAY:
                # Cycle found! Reconstruct it by following parent pointers
                cycle = [neighbor, vertex]
                current = vertex
                while parent[current] != -1 and parent[current] != neighbor:
                    current = parent[current]
                    cycle.append(current)
                cycle.append(neighbor)  # Complete the cycle
                return cycle[::-1]
            
            elif color[neighbor] == Color.WHITE:
                parent[neighbor] = vertex
                result = self._dfs_find_cycle(neighbor, color, parent)
                if result:
                    return result
        
        color[vertex] = Color.BLACK
        return None
 
 
# Example usage demonstrating directed cycle detection
if __name__ == "__main__":
    # Graph with cycle: 0 → 1 → 2 → 0
    g1 = DirectedGraph(4)
    g1.add_edge(0, 1)
    g1.add_edge(1, 2)
    g1.add_edge(2, 0)  # Creates cycle
    g1.add_edge(2, 3)
    
    print(f"Graph 1 has cycle: {g1.has_cycle()}")  # True
    print(f"Cycle found: {g1.find_cycle()}")  # [0, 1, 2, 0]
    
    # DAG (no cycle)
    g2 = DirectedGraph(4)
    g2.add_edge(0, 1)
    g2.add_edge(0, 2)
    g2.add_edge(1, 3)
    g2.add_edge(2, 3)
    
    print(f"Graph 2 has cycle: {g2.has_cycle()}")  # False
    
    # Graph with cross edge but no cycle
    # 0 → 1 → 3
    # ↓       ↑
    # 2 ──────┘
    g3 = DirectedGraph(4)
    g3.add_edge(0, 1)
    g3.add_edge(0, 2)
    g3.add_edge(1, 3)
    g3.add_edge(2, 3)  # Cross edge, NOT a cycle
    
    print(f"Graph 3 has cycle: {g3.has_cycle()}")  # False

The Recursion Stack Alternative

Instead of three colors, you can use a separate inStack[] boolean array alongside visited[] . The vertex is 'gray' when visited[v] && inStack[v], and 'black' when visited[v] && !inStack[v] . Both approaches are equivalent. The three-color version is more conceptually elegant; the in-stack version may be clearer for some implementations.

Visual Walkthrough: Step-by-Step Execution

Let's trace through the three-color algorithm on two graphs: one with a cycle, one without. Example 1: Graph WITH Cycle Edges: 0\to1, 1\to2, 2\to3, 3\to1 (cycle: 1\to2\to3\to1) Starting DFS from vertex 0:

Trace of Graph WITH Cycle
Step	Action	Vertex 0	Vertex 1	Vertex 2	Vertex 3	Result
1	Start DFS(0)	GRAY	WHITE	WHITE	WHITE	Continue
2	DFS(1) from 0	GRAY	GRAY	WHITE	WHITE	Continue
3	DFS(2) from 1	GRAY	GRAY	GRAY	WHITE	Continue
4	DFS(3) from 2	GRAY	GRAY	GRAY	GRAY	Continue
5	3's neighbor is 1	GRAY	GRAY	GRAY	GRAY	1 is GRAY → CYCLE!

At step 5, vertex 3 examines its neighbor (vertex 1). Vertex 1 is GRAY, meaning it's currently in our DFS path: 0\to1\to2\to3. Finding an edge from 3 back to 1 creates the cycle 1\to2\to3\to1. Example 2: Graph WITHOUT Cycle (but with cross edge) Edges: 0\to1, 0\to2, 1\to3, 2\to3 This graph has two paths to 3: 0\to1\to3 and 0\to2\to3.

Trace of Graph WITHOUT Cycle
Step	Action	Vertex 0	Vertex 1	Vertex 2	Vertex 3	Result
1	Start DFS(0)	GRAY	WHITE	WHITE	WHITE	Continue
2	DFS(1) from 0	GRAY	GRAY	WHITE	WHITE	Continue
3	DFS(3) from 1	GRAY	GRAY	WHITE	GRAY	Continue
4	3 done, backtrack	GRAY	GRAY	WHITE	BLACK	Continue
5	1 done, backtrack	GRAY	BLACK	WHITE	BLACK	Continue
6	DFS(2) from 0	GRAY	BLACK	GRAY	BLACK	Continue
7	2's neighbor is 3	GRAY	BLACK	GRAY	BLACK	3 is BLACK → No cycle
8	2 done, 0 done	BLACK	BLACK	BLACK	BLACK	Complete

At step 7, vertex 2 examines neighbor 3. Vertex 3 is BLACK (fully processed), not GRAY. This is a cross edge —it goes to a vertex that was completed in a different branch of exploration. No cycle exists.

The Color Transition Timeline

Every vertex follows the same color progression: WHITE \to GRAY \to BLACK. A vertex becomes GRAY when we start exploring it, and BLACK when we finish exploring all its descendants. A back edge (cycle) requires going from current GRAY vertex to another GRAY vertex—one that we started but haven't finished yet.

Alternative: Explicit Recursion Stack Tracking

Some implementations use two separate arrays instead of the three-color scheme: visited[] : Has this vertex ever been discovered? (White vs non-White) inStack[] (or recStack[]): Is this vertex currently in our DFS path? (Gray vs Black) This is functionally equivalent to three colors but can be more intuitive for some programmers.

recursion_stack_approach.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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
from collections import defaultdict
 
class DirectedGraphRecStack:
    """
    Directed cycle detection using explicit recursion stack tracking.
    """
    
    def __init__(self, vertices: int):
        self.V = vertices
        self.adj: dict[int, list[int]] = defaultdict(list)
    
    def add_edge(self, u: int, v: int) -> None:
        self.adj[u].append(v)
    
    def has_cycle(self) -> bool:
        """
        Detect cycle using visited and in_stack arrays.
        
        visited[v] = True means we've seen v at some point
        in_stack[v] = True means v is in our current DFS path
        
        Cycle exists if we find edge to vertex that's in_stack
        """
        visited = [False] * self.V
        in_stack = [False] * self.V
        
        for vertex in range(self.V):
            if not visited[vertex]:
                if self._dfs(vertex, visited, in_stack):
                    return True
        return False
    
    def _dfs(
        self, 
        vertex: int, 
        visited: list[bool], 
        in_stack: list[bool]
    ) -> bool:
        """
        DFS with explicit stack tracking.
        """
        visited[vertex] = True
        in_stack[vertex] = True  # Add to current path
        
        for neighbor in self.adj[vertex]:
            # If neighbor is in current DFS path → CYCLE
            if in_stack[neighbor]:
                return True
            
            # If not visited, explore it
            if not visited[neighbor]:
                if self._dfs(neighbor, visited, in_stack):
                    return True
            
            # If visited but NOT in stack, it was completed
            # in a different path → no cycle from this edge
        
        # Remove from stack (backtracking)
        in_stack[vertex] = False
        return False
 
 
class DirectedGraphIterative:
    """
    Iterative DFS for cycle detection - avoids stack overflow.
    """
    
    def __init__(self, vertices: int):
        self.V = vertices
        self.adj: dict[int, list[int]] = defaultdict(list)
    
    def add_edge(self, u: int, v: int) -> None:
        self.adj[u].append(v)
    
    def has_cycle(self) -> bool:
        """
        Iterative DFS cycle detection using explicit stack.
        
        Uses state machine: each vertex on stack has an iterator
        position to track which neighbors are yet to be explored.
        """
        WHITE, GRAY, BLACK = 0, 1, 2
        color = [WHITE] * self.V
        
        for source in range(self.V):
            if color[source] != WHITE:
                continue
            
            # Stack contains (vertex, iterator over neighbors)
            stack = [(source, iter(self.adj[source]))]
            color[source] = GRAY
            
            while stack:
                vertex, neighbors = stack[-1]
                
                try:
                    neighbor = next(neighbors)
                    
                    if color[neighbor] == GRAY:
                        # Back edge - CYCLE!
                        return True
                    elif color[neighbor] == WHITE:
                        # Explore unvisited neighbor
                        color[neighbor] = GRAY
                        stack.append((neighbor, iter(self.adj[neighbor])))
                    # If BLACK, cross/forward edge - continue
                    
                except StopIteration:
                    # Done with all neighbors
                    stack.pop()
                    color[vertex] = BLACK
        
        return False
 
 
# Verify both implementations agree
def test_implementations():
    """Test that both approaches give same results."""
    test_cases = [
        # (edges, expected_has_cycle)
        ([(0, 1), (1, 2), (2, 0)], True),   # Triangle cycle
        ([(0, 1), (0, 2), (1, 3), (2, 3)], False),  # DAG with cross edge
        ([(0, 1), (1, 2), (2, 3), (3, 1)], True),   # Cycle: 1→2→3→1
        ([(0, 1)], False),  # Single edge
        ([], False),  # No edges
    ]
    
    for edges, expected in test_cases:
        n = max([max(e) for e in edges]) + 1 if edges else 1
        
        g1 = DirectedGraphRecStack(n)
        g2 = DirectedGraphIterative(n)
        
        for u, v in edges:
            g1.add_edge(u, v)
            g2.add_edge(u, v)
        
        r1, r2 = g1.has_cycle(), g2.has_cycle()
        assert r1 == r2 == expected, f"Failed: {edges}"
    
    print("All tests passed!")
 
test_implementations()

Three-Color Advantages

•Single array instead of two
•Clear semantic meaning for each state
•Aligns with academic literature
•Easy to reason about correctness

Recursion Stack Advantages

•Boolean arrays may be more intuitive
•Explicit 'in path' semantics
•Easier to extend for cycle reconstruction
•Maps directly to actual recursion behavior

Kahn's Algorithm: Detecting Cycles via Topological Sort

There's an elegant alternative for cycle detection: Kahn's algorithm for topological sorting . The key insight is: A directed graph has a valid topological ordering if and only if it has no cycles (is a DAG). Kahn's algorithm works by repeatedly removing vertices with no incoming edges. If the graph is acyclic, we'll eventually remove all vertices. If a cycle exists, vertices in the cycle will never have zero incoming edges (each depends on another in the cycle), so we'll get stuck. Algorithm: Compute in-degree for all vertices Add all vertices with in-degree 0 to a queue While queue is not empty: Remove a vertex v, add to result Decrease in-degree of all v's neighbors If any neighbor's in-degree becomes 0, add to queue If result contains fewer than V vertices \to CYCLE EXISTS

kahns_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
from collections import deque, defaultdict
 
def has_cycle_kahn(vertices: int, edges: list[tuple[int, int]]) -> bool:
    """
    Detect cycle using Kahn's algorithm (BFS-based topological sort).
    
    If topological sort processes all vertices, no cycle exists.
    If some vertices remain unprocessed, they're part of a cycle.
    
    Time: O(V + E)
    Space: O(V + E)
    """
    # Build adjacency list and compute in-degrees
    adj: dict[int, list[int]] = defaultdict(list)
    in_degree = [0] * vertices
    
    for u, v in edges:
        adj[u].append(v)
        in_degree[v] += 1
    
    # Initialize queue with all vertices having in-degree 0
    queue = deque()
    for v in range(vertices):
        if in_degree[v] == 0:
            queue.append(v)
    
    processed_count = 0
    
    while queue:
        vertex = queue.popleft()
        processed_count += 1
        
        for neighbor in adj[vertex]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # If we processed all vertices, no cycle
    # If some remain, they're in cycles (never reached 0 in-degree)
    return processed_count < vertices
 
 
def find_cycle_vertices_kahn(
    vertices: int, 
    edges: list[tuple[int, int]]
) -> list[int]:
    """
    Find all vertices that are part of cycles.
    
    Returns list of vertices that couldn't be topologically sorted.
    """
    adj: dict[int, list[int]] = defaultdict(list)
    in_degree = [0] * vertices
    
    for u, v in edges:
        adj[u].append(v)
        in_degree[v] += 1
    
    queue = deque([v for v in range(vertices) if in_degree[v] == 0])
    processed = set()
    
    while queue:
        vertex = queue.popleft()
        processed.add(vertex)
        
        for neighbor in adj[vertex]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # Vertices not processed are in cycles
    return [v for v in range(vertices) if v not in processed]
 
 
# Examples
print(has_cycle_kahn(4, [(0, 1), (1, 2), (2, 3), (3, 1)]))  # True
print(has_cycle_kahn(4, [(0, 1), (0, 2), (1, 3), (2, 3)]))  # False
 
print(find_cycle_vertices_kahn(5, [(0, 1), (1, 2), (2, 3), (3, 1), (3, 4)]))
# Output: [1, 2, 3] - these vertices are in the cycle

When to Use Kahn's Approach

Kahn's algorithm is ideal when you also need a topological ordering, or when you want to identify ALL vertices involved in cycles (not just detect one cycle). It's BFS-based, so it avoids recursion depth issues. However, it doesn't easily give you the actual cycle path—just which vertices are 'stuck.'

Connection to Strongly Connected Components

Cycle detection is intimately related to a more general concept: Strongly Connected Components (SCCs) . Definition: A strongly connected component is a maximal set of vertices such that every vertex is reachable from every other vertex in the set. Key Insight: A directed graph has a cycle if and only if it has a strongly connected component with more than one vertex. If vertices A and B are in the same SCC, there's a path from A to B and from B to A. These two paths together form at least one cycle. Implications: Finding SCCs gives you a complete picture of the graph's cyclic structure SCCs with size > 1 contain cycles SCCs with size = 1 might contain a self-loop (still a cycle) Algorithms like Tarjan's or Kosaraju's find all SCCs in O(V + E) time, effectively solving cycle detection as a byproduct.

Cycle Detection vs SCC Algorithms
Approach	Time	Detects Cycles	Finds All SCCs	Returns Cycle Path
Three-Color DFS	O(V+E)	Yes	No	Yes (with modification)
Kahn's Algorithm	O(V+E)	Yes	No	No (but finds cycle vertices)
Tarjan's SCC	O(V+E)	Yes (byproduct)	Yes	No (but gives SCC groupings)
Kosaraju's SCC	O(V+E)	Yes (byproduct)	Yes	No (but gives SCC groupings)

When to Use SCC Algorithms

If you only need to know WHETHER a cycle exists, use three-color DFS—it's simplest. If you need to understand the full cyclic structure, identify all cycles, or condense the graph into a DAG of SCCs, use Tarjan's or Kosaraju's algorithm. SCC algorithms provide more information but are more complex to implement.

Edge Cases and Common Pitfalls

Directed cycle detection has several subtle cases that can cause bugs if not handled properly:

Critical Edge Cases

•Self-Loops: Edge (v, v) is a cycle of length 1. Three-color DFS handles this correctly—when at v (GRAY), we check neighbor v which is GRAY → cycle detected.
•Disconnected Graphs: Must start DFS from all unvisited vertices, not just vertex 0. A cycle might exist in a component unreachable from 0.
•Parallel Edges: Multiple edges from A to B don't create cycles (unlike undirected graphs). Only the existence of a back edge matters.
•Empty Graph: Zero vertices or zero edges → no cycle.
•Single Vertex, No Edges: No cycle (no self-loop).
•Confusing Cross Edges with Back Edges: The most common bug! Cross edges go to BLACK vertices, back edges go to GRAY vertices. Only back edges indicate cycles.

edge_cases_test.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
def test_edge_cases(graph_class):
    """
    Comprehensive edge case testing for cycle detection.
    """
    # Test 1: Self-loop
    g1 = graph_class(3)
    g1.add_edge(0, 1)
    g1.add_edge(1, 1)  # Self-loop on vertex 1
    assert g1.has_cycle() == True, "Should detect self-loop"
    
    # Test 2: Empty graph
    g2 = graph_class(0)
    assert g2.has_cycle() == False, "Empty graph has no cycle"
    
    # Test 3: Single vertex, no edges
    g3 = graph_class(1)
    assert g3.has_cycle() == False, "Single vertex, no self-loop"
    
    # Test 4: Disconnected - cycle in unreachable component
    g4 = graph_class(5)
    g4.add_edge(0, 1)  # Component 1: just an edge
    g4.add_edge(2, 3)
    g4.add_edge(3, 4)
    g4.add_edge(4, 2)  # Component 2: cycle 2→3→4→2
    assert g4.has_cycle() == True, "Should find cycle in second component"
    
    # Test 5: Cross edge (looks like cycle but isn't)
    g5 = graph_class(4)
    g5.add_edge(0, 1)
    g5.add_edge(0, 2)
    g5.add_edge(1, 3)
    g5.add_edge(2, 3)  # Cross edge to already-processed 3
    assert g5.has_cycle() == False, "Cross edge is not a cycle"
    
    # Test 6: Forward edge (also not a cycle)
    g6 = graph_class(3)
    g6.add_edge(0, 1)
    g6.add_edge(1, 2)
    g6.add_edge(0, 2)  # Forward edge: 0→2 but 0→1→2 exists
    assert g6.has_cycle() == False, "Forward edge is not a cycle"
    
    # Test 7: Long cycle
    g7 = graph_class(100)
    for i in range(99):
        g7.add_edge(i, i + 1)
    g7.add_edge(99, 0)  # Complete the cycle
    assert g7.has_cycle() == True, "Should detect long cycle"
    
    print("All edge case tests passed!")
 
# Run with your DirectedGraph implementation
# test_edge_cases(DirectedGraph)

2 / 4

Comparing Undirected vs Directed Cycle Detection

Aspect

Undirected Graph

Directed Graph

What indicates cycle?

Any edge to visited non-parent

Only edge to ancestor in current path

Edge types

Tree edges, Back edges only

Tree, Back, Forward, Cross edges

Sufficient tracking

visited[] array

Need recursion stack state

Parent tracking

Required to avoid false positives

Not needed (edges are one-way)

Cross edges

Don't exist (would be back edges)

Exist and must not trigger false positive

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

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

from collections import defaultdict from enum import Enum from typing import Optional class Color(Enum): """ Three-color states for directed graph DFS. """ WHITE = 0 # Unvisited GRAY = 1 # Currently in DFS path (in progress) BLACK = 2 # Completely processed class DirectedGraph: """ Directed graph with cycle detection using three-color DFS. """ def __init__(self, vertices: int): self.V = vertices self.adj: dict[int, list[int]] = defaultdict(list) def add_edge(self, u: int, v: int) -> None: """Add directed edge from u to v.""" self.adj[u].append(v) def has_cycle(self) -> bool: """ Detect if the directed graph contains a cycle. Uses three-color DFS: - WHITE: unvisited - GRAY: currently in DFS stack (being processed) - BLACK: completely finished A cycle exists iff we find a GRAY → GRAY edge (back edge). Time Complexity: O(V + E) Space Complexity: O(V) """ color = [Color.WHITE] * self.V for vertex in range(self.V): if color[vertex] == Color.WHITE: if self._dfs_has_cycle(vertex, color): return True return False def _dfs_has_cycle(self, vertex: int, color: list[Color]) -> bool: """ DFS helper for cycle detection. Returns True if cycle is found starting from vertex. """ # Mark as gray (in progress / in current DFS path) color[vertex] = Color.GRAY for neighbor in self.adj[vertex]: if color[neighbor] == Color.GRAY: # Found edge to vertex in current path - CYCLE! return True elif color[neighbor] == Color.WHITE: # Explore unvisited neighbor if self._dfs_has_cycle(neighbor, color): return True # If BLACK, neighbor was fully processed in different path # This is a cross edge or forward edge - NOT a cycle # Mark as black (completely processed) color[vertex] = Color.BLACK return False def find_cycle(self) -> Optional[list[int]]: """ Find and return a cycle if one exists. Returns: List of vertices forming the cycle, or None if no cycle. """ color = [Color.WHITE] * self.V parent = [-1] * self.V for vertex in range(self.V): if color[vertex] == Color.WHITE: cycle = self._dfs_find_cycle(vertex, color, parent) if cycle: return cycle return None def _dfs_find_cycle( self, vertex: int, color: list[Color], parent: list[int] ) -> Optional[list[int]]: """ DFS helper that returns the cycle path when found. """ color[vertex] = Color.GRAY for neighbor in self.adj[vertex]: if color[neighbor] == Color.GRAY: # Cycle found! Reconstruct it by following parent pointers cycle = [neighbor, vertex] current = vertex while parent[current] != -1 and parent[current] != neighbor: current = parent[current] cycle.append(current) cycle.append(neighbor) # Complete the cycle return cycle[::-1] elif color[neighbor] == Color.WHITE: parent[neighbor] = vertex result = self._dfs_find_cycle(neighbor, color, parent) if result: return result color[vertex] = Color.BLACK return None # Example usage demonstrating directed cycle detection if __name__ == "__main__": # Graph with cycle: 0 → 1 → 2 → 0 g1 = DirectedGraph(4) g1.add_edge(0, 1) g1.add_edge(1, 2) g1.add_edge(2, 0) # Creates cycle g1.add_edge(2, 3) print(f"Graph 1 has cycle: {g1.has_cycle()}") # True print(f"Cycle found: {g1.find_cycle()}") # [0, 1, 2, 0] # DAG (no cycle) g2 = DirectedGraph(4) g2.add_edge(0, 1) g2.add_edge(0, 2) g2.add_edge(1, 3) g2.add_edge(2, 3) print(f"Graph 2 has cycle: {g2.has_cycle()}") # False # Graph with cross edge but no cycle # 0 → 1 → 3 # ↓ ↑ # 2 ──────┘ g3 = DirectedGraph(4) g3.add_edge(0, 1) g3.add_edge(0, 2) g3.add_edge(1, 3) g3.add_edge(2, 3) # Cross edge, NOT a cycle print(f"Graph 3 has cycle: {g3.has_cycle()}") # False

Trace of Graph WITH Cycle

Step

Action

Vertex 0

Vertex 1

Vertex 2

Vertex 3

Result

Start DFS(0)

GRAY

WHITE

Continue

DFS(1) from 0

GRAY

WHITE

Continue

DFS(2) from 1

GRAY

WHITE

Continue

DFS(3) from 2

GRAY

Continue

3's neighbor is 1

GRAY

1 is GRAY → CYCLE!

Trace of Graph WITHOUT Cycle

Step

Action

Vertex 0

Vertex 1

Vertex 2

Vertex 3

Result

Start DFS(0)

GRAY

WHITE

Continue

DFS(1) from 0

GRAY

WHITE

Continue

DFS(3) from 1

GRAY

WHITE

GRAY

Continue

3 done, backtrack

GRAY

WHITE

BLACK

Continue

1 done, backtrack

GRAY

BLACK

WHITE

BLACK

Continue

DFS(2) from 0

GRAY

BLACK

GRAY

BLACK

Continue

2's neighbor is 3

GRAY

BLACK

GRAY

BLACK

3 is BLACK → No cycle

2 done, 0 done

BLACK

Complete

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

136

137

138

139

140

141

142

143

from collections import defaultdict class DirectedGraphRecStack: """ Directed cycle detection using explicit recursion stack tracking. """ def __init__(self, vertices: int): self.V = vertices self.adj: dict[int, list[int]] = defaultdict(list) def add_edge(self, u: int, v: int) -> None: self.adj[u].append(v) def has_cycle(self) -> bool: """ Detect cycle using visited and in_stack arrays. visited[v] = True means we've seen v at some point in_stack[v] = True means v is in our current DFS path Cycle exists if we find edge to vertex that's in_stack """ visited = [False] * self.V in_stack = [False] * self.V for vertex in range(self.V): if not visited[vertex]: if self._dfs(vertex, visited, in_stack): return True return False def _dfs( self, vertex: int, visited: list[bool], in_stack: list[bool] ) -> bool: """ DFS with explicit stack tracking. """ visited[vertex] = True in_stack[vertex] = True # Add to current path for neighbor in self.adj[vertex]: # If neighbor is in current DFS path → CYCLE if in_stack[neighbor]: return True # If not visited, explore it if not visited[neighbor]: if self._dfs(neighbor, visited, in_stack): return True # If visited but NOT in stack, it was completed # in a different path → no cycle from this edge # Remove from stack (backtracking) in_stack[vertex] = False return False class DirectedGraphIterative: """ Iterative DFS for cycle detection - avoids stack overflow. """ def __init__(self, vertices: int): self.V = vertices self.adj: dict[int, list[int]] = defaultdict(list) def add_edge(self, u: int, v: int) -> None: self.adj[u].append(v) def has_cycle(self) -> bool: """ Iterative DFS cycle detection using explicit stack. Uses state machine: each vertex on stack has an iterator position to track which neighbors are yet to be explored. """ WHITE, GRAY, BLACK = 0, 1, 2 color = [WHITE] * self.V for source in range(self.V): if color[source] != WHITE: continue # Stack contains (vertex, iterator over neighbors) stack = [(source, iter(self.adj[source]))] color[source] = GRAY while stack: vertex, neighbors = stack[-1] try: neighbor = next(neighbors) if color[neighbor] == GRAY: # Back edge - CYCLE! return True elif color[neighbor] == WHITE: # Explore unvisited neighbor color[neighbor] = GRAY stack.append((neighbor, iter(self.adj[neighbor]))) # If BLACK, cross/forward edge - continue except StopIteration: # Done with all neighbors stack.pop() color[vertex] = BLACK return False # Verify both implementations agree def test_implementations(): """Test that both approaches give same results.""" test_cases = [ # (edges, expected_has_cycle) ([(0, 1), (1, 2), (2, 0)], True), # Triangle cycle ([(0, 1), (0, 2), (1, 3), (2, 3)], False), # DAG with cross edge ([(0, 1), (1, 2), (2, 3), (3, 1)], True), # Cycle: 1→2→3→1 ([(0, 1)], False), # Single edge ([], False), # No edges ] for edges, expected in test_cases: n = max([max(e) for e in edges]) + 1 if edges else 1 g1 = DirectedGraphRecStack(n) g2 = DirectedGraphIterative(n) for u, v in edges: g1.add_edge(u, v) g2.add_edge(u, v) r1, r2 = g1.has_cycle(), g2.has_cycle() assert r1 == r2 == expected, f"Failed: {edges}" print("All tests passed!") test_implementations()

from collections import deque, defaultdict def has_cycle_kahn(vertices: int, edges: list[tuple[int, int]]) -> bool: """ Detect cycle using Kahn's algorithm (BFS-based topological sort). If topological sort processes all vertices, no cycle exists. If some vertices remain unprocessed, they're part of a cycle. Time: O(V + E) Space: O(V + E) """ # Build adjacency list and compute in-degrees adj: dict[int, list[int]] = defaultdict(list) in_degree = [0] * vertices for u, v in edges: adj[u].append(v) in_degree[v] += 1 # Initialize queue with all vertices having in-degree 0 queue = deque() for v in range(vertices): if in_degree[v] == 0: queue.append(v) processed_count = 0 while queue: vertex = queue.popleft() processed_count += 1 for neighbor in adj[vertex]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor) # If we processed all vertices, no cycle # If some remain, they're in cycles (never reached 0 in-degree) return processed_count < vertices def find_cycle_vertices_kahn( vertices: int, edges: list[tuple[int, int]] ) -> list[int]: """ Find all vertices that are part of cycles. Returns list of vertices that couldn't be topologically sorted. """ adj: dict[int, list[int]] = defaultdict(list) in_degree = [0] * vertices for u, v in edges: adj[u].append(v) in_degree[v] += 1 queue = deque([v for v in range(vertices) if in_degree[v] == 0]) processed = set() while queue: vertex = queue.popleft() processed.add(vertex) for neighbor in adj[vertex]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor) # Vertices not processed are in cycles return [v for v in range(vertices) if v not in processed] # Examples print(has_cycle_kahn(4, [(0, 1), (1, 2), (2, 3), (3, 1)])) # True print(has_cycle_kahn(4, [(0, 1), (0, 2), (1, 3), (2, 3)])) # False print(find_cycle_vertices_kahn(5, [(0, 1), (1, 2), (2, 3), (3, 1), (3, 4)])) # Output: [1, 2, 3] - these vertices are in the cycle

Cycle Detection vs SCC Algorithms

Approach

Time

Detects Cycles

Finds All SCCs

Returns Cycle Path

Three-Color DFS

O(V+E)

Yes

Yes (with modification)

Kahn's Algorithm

O(V+E)

Yes

No (but finds cycle vertices)

Tarjan's SCC

O(V+E)

Yes (byproduct)

Yes

No (but gives SCC groupings)

Kosaraju's SCC

O(V+E)

Yes (byproduct)

Yes

No (but gives SCC groupings)

def test_edge_cases(graph_class): """ Comprehensive edge case testing for cycle detection. """ # Test 1: Self-loop g1 = graph_class(3) g1.add_edge(0, 1) g1.add_edge(1, 1) # Self-loop on vertex 1 assert g1.has_cycle() == True, "Should detect self-loop" # Test 2: Empty graph g2 = graph_class(0) assert g2.has_cycle() == False, "Empty graph has no cycle" # Test 3: Single vertex, no edges g3 = graph_class(1) assert g3.has_cycle() == False, "Single vertex, no self-loop" # Test 4: Disconnected - cycle in unreachable component g4 = graph_class(5) g4.add_edge(0, 1) # Component 1: just an edge g4.add_edge(2, 3) g4.add_edge(3, 4) g4.add_edge(4, 2) # Component 2: cycle 2→3→4→2 assert g4.has_cycle() == True, "Should find cycle in second component" # Test 5: Cross edge (looks like cycle but isn't) g5 = graph_class(4) g5.add_edge(0, 1) g5.add_edge(0, 2) g5.add_edge(1, 3) g5.add_edge(2, 3) # Cross edge to already-processed 3 assert g5.has_cycle() == False, "Cross edge is not a cycle" # Test 6: Forward edge (also not a cycle) g6 = graph_class(3) g6.add_edge(0, 1) g6.add_edge(1, 2) g6.add_edge(0, 2) # Forward edge: 0→2 but 0→1→2 exists assert g6.has_cycle() == False, "Forward edge is not a cycle" # Test 7: Long cycle g7 = graph_class(100) for i in range(99): g7.add_edge(i, i + 1) g7.add_edge(99, 0) # Complete the cycle assert g7.has_cycle() == True, "Should detect long cycle" print("All edge case tests passed!") # Run with your DirectedGraph implementation # test_edge_cases(DirectedGraph)

Cycle Detection in Directed Graphs

When Direction Changes Everything

Why the Undirected Approach Fails for Directed Graphs

The Three-Color DFS Algorithm

Visual Walkthrough: Step-by-Step Execution

Alternative: Explicit Recursion Stack Tracking

Kahn's Algorithm: Detecting Cycles via Topological Sort

Connection to Strongly Connected Components

Edge Cases and Common Pitfalls

There’s more to understand.

Cycle Detection in Directed Graphs

When Direction Changes Everything

Why the Undirected Approach Fails for Directed Graphs

The Three-Color DFS Algorithm

Visual Walkthrough: Step-by-Step Execution

Alternative: Explicit Recursion Stack Tracking

Kahn's Algorithm: Detecting Cycles via Topological Sort

Connection to Strongly Connected Components

Edge Cases and Common Pitfalls

There’s more to understand.