Sign in to watch this lesson
Algorithms - Graphs I · 3:59
Topological Sort and DAG DP
A topological order lines up the vertices of a directed graph so every arrow points forward, and it exists exactly when there is no cycle. We build one two ways on six start-of-day jobs: reversing the DFS finishing order (5 4 1 0 3 2) and Kahn's algorithm, which peels vertices with in-degree zero (4 5 1 0 3 2), checks for cycles and tells you when the order is unique. Then a single left-to-right DP sweep over that order gives the earliest finish times, a 10-minute morning, and its critical chain 4 0 3 2.
You will learn
- Produce a topological order in O(n + m) by reversing DFS finishing times, and explain why it is valid
- Run Kahn's algorithm, use it to detect cycles (fewer than n vertices output) and to decide whether the order is unique
- Solve longest-path and scheduling problems on a DAG with one DP sweep in topological order, and restore a critical chain
- Avoid the classic bugs: forgetting to reverse, assuming uniqueness, starting unreachable vertices at 0 instead of minus infinity, overflow in path counts