Advanced · Module 13 · Lesson 5 of 5
Topological sort
A topological order lists the vertices of a directed acyclic graph so that every edge points forward: everything comes after what it depends on. Kahn's algorithm builds one with in-degrees and a queue, and detects cycles for free.
By the end you can
- Explain what a topological order is and when one exists
- Compute one with Kahn's algorithm, using in-degrees and a queue
- Compute one with depth-first search by reversing the finish order, and detect impossible orders
Builds on Cycles and connected components.
01 · A question first
A build has 2,000 targets, each depending on others. In what order should they be compiled, so that nothing is built before what it needs? And how do you prove that no order exists when two targets depend on each other?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Ordering by dependencies
- Kahn's algorithm
- The depth-first version
- One order among many
- Mistakes to avoid
- Real systems
- The end of the Core graphs module
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
03 · Practice
Asked in interviews
Something wrong with this lesson? Report a problem