Topological Sort: Ordering Tasks So Every Edge Points Forwards

A topological sort puts the vertices of a directed graph in a line so that every edge points forwards: for each edge u->v, u comes before v. Read the edges as dependencies, "u must happen before v", and the line is an order in which to do the tasks. This card defines the order, says which graphs have one, and introduces the count that both methods in Topological Sort are built on.

An order exists only in a directed acyclic graph, one with no directed cycle. If A must come before B and B before A, no line can put both first. Every directed acyclic graph has at least one order, and usually several.

The graph below is the one the topic uses. It has six vertices and six edges, and it has no cycle.

C D A B E F is a topological order of it: check each edge and its tail always comes first. D C B E A F is another. A B C D E F is not, because D->A points backwards.

A vertex's in-degree is the number of edges coming into it, which here is the number of tasks it waits on. A is waiting on 1, D; B on 2, C and D; F on 2, A and B; and C and D on nothing. A vertex with in-degree 0 can go first, because nothing has to happen before it. Kahn's algorithm, traced on Trace Kahn's Algorithm With In-Degrees and a Queue of Ready Tasks, repeats exactly that observation.

Getting dressed is a topological sort: socks before shoes, shirt before tie, and between socks and shirt it does not matter which comes first. The picture breaks because a person can pull on a sock and a shoe together and start again, while a topological order puts each task in exactly one place, once.

Reach for a topological sort when a problem talks about prerequisites, build order, dependencies, or steps that must come after other steps: course plans, compiling modules, spreadsheet cells that refer to other cells, and the order of jobs on a project.