Topological sort, explained

Imagine a list of tasks where some must be done before others: you must put on socks before shoes. Topological sort finds an order that respects all of those rules.

It only works on a directed graph with no cycles. If tasks depend on each other in a circle, no valid order exists, and the algorithm can tell you.

How it works

• Find nodes that have no incoming edges. They have no prerequisites.
• Add one of them to the order and remove it, with its outgoing edges, from the graph.
• Some other nodes now have no incoming edges. Repeat.
• If nodes remain but none can be taken, the graph has a cycle and no order exists.

A small example

Take these directed edges:

A>B  A>C  B>D  C>D

A valid order: A, B, C, D

A, C, B, D is also valid. When tasks do not depend on each other, more than one order can work.

What to know about its cost

• O(V + E) time.
• Uses O(V) space.
• Needs a directed graph with no cycles.

Where it works well

• Perfect for ordering tasks, builds and course prerequisites.
• Detects cycles as a side effect.

Where it struggles

• Does not work if there is a cycle.
• The answer is often not unique.

Try it yourself

Open the Graph Algorithms experiment, enter these edges (A>B, A>C, B>D, C>D), choose Topological sort, and step through it. Then try a different graph and watch how the result changes.

Open the Graph Algorithms experiment