Detecting Cycles During Topological Sort
You'll learn how both Kahn's algorithm and DFS-based topological sort naturally detect cycles, making topological sorting impossible when cycles exist.
Why Cycle Detection Matters
Topological sorting only works on Directed Acyclic Graphs (DAGs). If a cycle exists, there's no valid ordering—each vertex in the cycle depends on another in a circular way. Fortunately, both topological sort algorithms automatically detect cycles as a byproduct of their operation.
Kahn's Algorithm Cycle Detection
Kahn's algorithm processes vertices with in-degree zero. If a cycle exists, vertices in the cycle will always have non-zero in-degrees (they point to each other), so they'll never enter the queue.
Detection mechanism: After processing, if the number of vertices added to the topological order is less than the total number of vertices, a cycle exists.
processed_count = 0
while queue is not empty:
process vertex
processed_count += 1
if processed_count < total_vertices:
# Cycle detected!
DFS-Based Cycle Detection
The DFS approach uses a three-state tracking system you've seen in cycle detection:
- Unvisited: not yet explored
- Visiting: currently in the recursive call stack
- Visited: completely finished
Detection mechanism: If during DFS you encounter a vertex marked as "visiting," you've found a back edge—a cycle!
if neighbor is "visiting":
# Cycle detected!
Think of it like following a trail of breadcrumbs. If you step on a breadcrumb you dropped during your current walk, you've walked in a circle.
The Connection
Both methods fail gracefully when cycles exist: Kahn's leaves unprocessed vertices, while DFS finds back edges. This makes topological sort a convenient cycle-detection tool.
Key Takeaway: Cycle detection is built into topological sort—Kahn's algorithm detects cycles by counting processed vertices, while DFS detects cycles by identifying back edges to vertices still being processed.