Topological Sort

Put tasks in an order where every task comes after the tasks it depends on.

The idea (getting dressed)

You cannot put on shoes before socks, or a jacket before a shirt. Each arrow A → B means “A must happen before B”. A topological sort lists everything in an order that respects every arrow. Course prerequisites, build systems and task schedulers all need this.

Kahn’s algorithm does it by repeatedly doing what is allowed right now:

  1. For every task, count how many things it still waits for. This count is its indegree (arrows coming in).
  2. Tasks with indegree 0 wait for nothing. Put them in a queue.
  3. Take a task from the queue and add it to the answer. Then “cross out” its arrows: every task that waited on it now has one fewer thing to wait for. If a task reaches 0, queue it.

If you run out of tasks to take but some are still waiting, they are waiting on each other: that is a cycle, and no valid order exists.

Watch it work

Tasks are numbered from 0. At most 15 arrows.

Try it

Common mistakes

Complexity, in plain English: every task enters the queue at most once and every arrow is crossed out once, so the time is about the tasks plus the arrows (O(V + E)).