Course contentsShow
← Computer Science
Lesson 726 of 2,87217. Graph Traversal AlgorithmsFree lesson

Detecting Cycles During Topological Sort

Identify cycle detection mechanisms in both Kahn's and DFS approaches.

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.