Topological Sort — definition.
Definition
Linear ordering of a DAG consistent with its dependencies.
Complexity
Time O(V + E); space O(V).
When to use it
- Schedule tasks with prerequisite edges.
- Detect cycles in a directed graph.
- Any "must-happen-before" constraint.
Representative scenarios
- Build-Order Planner — order tasks with dependencies.
- Dialect Sorter — derive letter order from a sorted alien dictionary.
- Certification Track — sequence courses by prereqs.
Related patterns
Read the full pattern page: Topological Sort — template, code, and drills.
Run the free diagnostic.
Ten-minute patterns quiz. No card. Personalized loop starts on the other side.