Algorithms / Topological Sort Dag
Least You Need to Know: Topological Sort, DAG Dependencies, and Prerequisite Order
Topological sorting gives an order that respects directed dependencies: every edge points from something that must come earlier to something that may come later. It only works when the graph is a **DAG**.
The least you need to know
- A topological order places every prerequisite before each task that depends on it.
- Kahn's algorithm repeatedly removes nodes with indegree 0.
- A directed cycle blocks all valid topological orders.
- DFS can also produce a topological order by reversing finish order in a DAG.
- Topological sort is about dependency order, not shortest paths or connectivity.
Key notation
u → v
u must come before v
indegree(v)
number of incoming prerequisite edges into v
DAG
directed acyclic graph
Tiny worked example
- Suppose courses have prerequisite edges `A → B` meaning A before B.
- Any course with indegree 0 can be taken now.
- Remove it, reduce indegrees of its outgoing neighbors, and continue.
- If every course is removed, the produced order respects all prerequisites.
Common mistakes
- Students often forget that topological sort is for directed graphs, not arbitrary undirected ones.
- Students often think one valid order is unique when many DAGs allow several.
- Students often miss that leftover nodes after Kahn's algorithm imply a cycle.
How to recognize this kind of problem
- The prompt says prerequisite, dependency, build order, or task order.
- Edges mean one item must happen before another.
- A valid answer is an order that respects all dependency arrows.
Next recommended lesson
Continue through this topic with Least You Need to Know: Tree DP, Child-State Combination, and Rerooting Intuition.
Least You Need to Know: Tree DP, Child-State Combination, and Rerooting IntuitionRelated lessons
Keep going with nearby lessons in the same topic.