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.
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
Worked example
- Suppose courses have prerequisite edges
A → Bmeaning 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 it
- 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.