Topological Sort

Graphs: lesson 8 of 8

Order the steps so nothing runs before what it depends on.

Lesson 8 of 8 · 6 min

Step 1 of 13

ready

unpack

order

—

Each job is a node; each "must come first" rule is a directed edge. The number above each job counts its blockers.

The Idea

Some jobs must precede others, and the rest are free to happen in any order. Model each job as a node and each "must come first" rule as a directed edge. Kahn's algorithm repeatedly outputs any job whose blockers are all done. Leftovers at the end mean a cycle.

Real-World Example

Flat-pack furniture instructions. The brackets must be on before the legs go on, and the legs before the top — but unpacking the cushions can happen at any point. That is why two people assembling the same wardrobe follow different step orders and both finish with a working wardrobe.

The Code

after = {"unpack": ["frame", "legs"], "frame": ["top"], "legs": ["top"],
         "top": ["cushion"], "cushion": []}
indeg = {n: 0 for n in after}
for n in after:
    for m in after[n]:
        indeg[m] += 1                    # count each step's blockers
order, ready = [], [n for n in after if indeg[n] == 0]
while ready:
    n = ready.pop(0)                     # nothing is waiting on it
    order.append(n)
    for m in after[n]:
        indeg[m] -= 1
        if indeg[m] == 0:                # its last blocker cleared
            ready.append(m)
print(order)   # ['unpack', 'frame', 'legs', 'top', 'cushion']

Your turn

Put the steps in the right order.

Remove a ready step, output it, and decrement its dependents
Count how many blockers each step is waiting on
Collect every step whose count is already zero
Stop when nothing is ready; leftover steps mean a cycle

Mini quiz

1 / 3

Topological Sort