Lesson 173
Topological Sort
Ordering Dependencies
1:00How to linearly order the vertices of a directed acyclic graph so every dependency is satisfied — covering Kahn's in-degree algorithm, DFS reverse post-order, cycle detection, and when an ordering is unique.
By the end, you can
- Explain what a topological sort is and why it requires a directed acyclic graph.
- State the formal guarantee: for every edge u→v, u appears before v.
- Compute the in-degree of each vertex in a given DAG.
- Trace Kahn's algorithm step by step on a small graph, producing a valid topological order.
- Identify whether a graph contains a cycle using the output-length check.
- Explain why cycles prevent any valid topological ordering.
- Determine whether a DAG has a unique topological order or multiple valid orders.
- Describe the DFS-based alternative (reverse post-order) and state its time complexity.
- List real-world systems (build tools, schedulers, package managers, compilers) that rely on topological ordering to process items only after their dependencies.
Up next in Algorithms & Graph Algorithms
