Implementation
1"""
2Topological Sort - DFS (Reverse Post-Order)
3
4DFS-based topological sort explores depth-first, adding nodes to the result
5after all their descendants are processed, then reverses the result.
6
7Key Insight:
8 When DFS finishes a node (all descendants visited), that node has no
9 unprocessed dependencies "below" it. By reversing the finish order,
10 we get a valid topological order.
11
12Time Complexity: O(V + E) - visits every vertex and edge once
13Space Complexity: O(V) - recursion stack + visited set + result
14
15Advantages:
16 - Natural recursive structure
17 - Detects cycles during traversal
18 - Works well with existing DFS infrastructure
19
20Graph Representation:
21 Uses adjacency list format for DIRECTED graphs.
22 Format: {node: {successors}} where edges point FROM node TO successors.
23"""
24
25from typing import Dict, Set, List, Any
26
27
28def toposort(graph: Dict[Any, Set[Any]]) -> List[Any]:
29 """
30 Topological sort using DFS (reverse post-order).
31
32 Args:
33 graph: Adjacency list for directed graph {node: {successors}}
34
35 Returns:
36 List of nodes in topological order
37
38 Raises:
39 ValueError: If graph contains a cycle
40 """
41 visited = set()
42 in_stack = set() # For cycle detection
43 result = []
44
45 def _dfs(node: Any) -> None:
46 if node in in_stack:
47 raise ValueError(f"Graph contains a cycle involving node '{node}'")
48 if node in visited:
49 return
50
51 in_stack.add(node)
52
53 for neighbor in graph.get(node, set()):
54 _dfs(neighbor)
55
56 in_stack.remove(node)
57 visited.add(node)
58 result.append(node) # Add after all descendants processed
59
60 for node in graph:
61 if node not in visited:
62 _dfs(node)
63
64 return result[::-1] # Reverse for correct order
65
66
67# Example usage and demonstration
68if __name__ == "__main__":
69 # Example DAG (course prerequisites)
70 #
71 # A ──→ B ──→ D
72 # │ │
73 # ↓ ↓
74 # C ──→ E
75 #
76 example_dag = {
77 "A": {"B", "C"},
78 "B": {"D", "E"},
79 "C": {"E"},
80 "D": set(),
81 "E": set(),
82 }
83
84 print("Topological Sort (DFS):", toposort(example_dag))
85
86 # Example with cycle
87 cyclic_graph = {
88 "A": {"B"},
89 "B": {"C"},
90 "C": {"A"},
91 }
92
93 try:
94 toposort(cyclic_graph)
95 except ValueError as e:
96 print(f"Cycle detected: {e}")
97