Topological Sort Pattern
Topological sort linearizes a directed acyclic graph so each edge points forward. Kahn's algorithm (BFS on in-degrees) also detects cycles — if you can't order everything, a cycle exists.
Typical complexity: O(V + E) time, O(V) space
When to use it
- You have dependencies/prerequisites to order.
- The graph is directed and you need a valid sequence.
- You need to detect a cycle in a directed graph.
Practice problems
Read the approach or generate an interactive, step-by-step lesson:
Deep dive
Topological Sort: The Pattern for Dependency Ordering Problems
Learn how topological sorting works, why it only applies to DAGs, and how to solve course scheduling and dependency ordering problems.
Master topological sort by doing
codebrew.ai turns each problem into an interactive lesson — trace the algorithm variable by variable until the pattern clicks.
Start a free lesson