Lesson 24.1 · Topological Sort
Kahn's Algorithm
Repeatedly take a node with no remaining prerequisites (in-degree 0), output it, and remove its outgoing edges. If nodes remain stuck, there's a cycle.
14 min
Think of it like this
Getting dressed: socks before shoes, shirt before tie. At any moment you may put on anything whose "before" items are all on already, and there are often several valid orders.
1.In-degree queue
Count each node's in-degree. Queue every node with in-degree 0. Pop one, append it to the order, and decrement each successor's in-degree; any successor that drops to 0 joins the queue. When the queue empties, the order contains all nodes exactly when there's no cycle.
Several orders are usually valid. Using a PriorityQueue instead of a plain queue gives the lexicographically smallest one, which is handy when an exact answer is required.
edges = [[0,1],[0,2],[1,3],[2,3]]in-degree(map)
queue(queue)
order(list)
empty
Step 1/5Only 0 has no prerequisites.
Remember
- In-degree 0 = ready.
- Output count < n ⇒ cycle.
- PriorityQueue → smallest order.
Common mistakes
- Forgetting nodes with no edges at all (they have in-degree 0 and must be output too).
Words used in this lesson
- Topological order
- A list of a DAG's nodes where every edge points forward.
- In-degree
- The number of edges coming into a node: here, unfinished prerequisites.