Topological sorting

Every time you install software, build a program or plan a project, something has to work out what to do first. If task B needs task A, A must come earlier. A topological sort turns a web of such rules into one straight line.

A graph of nodes joined by one-way arrows, the placed nodes in green, and the order so far drawn as a row underneath
A graph of nodes joined by one-way arrows, the placed nodes in green, and the order so far drawn as a row underneath

The idea

Draw each task as a node and each rule "A before B" as an arrow from A to B. A topological order is a row of all the nodes in which every arrow points to the right. It is called a sort because it puts things in order, but unlike sorting numbers, it only has to respect the arrows: nodes that no chain of arrows connects may come in either order.

When it is impossible

If the arrows form a cycle, say A before B, B before C and C before A, then A would have to come before itself. So a topological order exists exactly when the graph has no directed cycle. A graph like that is called a directed acyclic graph, or DAG. Both methods below find a cycle if there is one, which makes them a handy cycle test too.

An example

Take the arrows A → C, B → C, B → D, C → E and D → E. Kahn's algorithm counts incoming arrows: A and B have none, so A goes first, then B. Removing B's arrows frees C and D, which follow, and then E: the order A, B, C, D, E. The DFS method visits A, then C, then E; E finishes first, then C, then A, each going to the front. Then it visits B and D, which finish in front of them: the order B, D, A, C, E. Both orders are correct.

Kahn or DFS?

Kahn's algorithm, published by Arthur Kahn in 1962, works forwards: it always knows which tasks are free to start now, which suits scheduling, and it can pick among free tasks by any rule, such as alphabetical order. The DFS method, popularised by Robert Tarjan in 1976, works backwards from the ends and needs only a depth-first search. Both take time that grows with the number of nodes plus edges.

Robert Tarjan, who with John Hopcroft showed in 1972–73 that depth-first search solves many graph problems in linear time; they received the 1986 Turing Award in part for that work.
Robert Tarjan, who with John Hopcroft showed in 1972–73 that depth-first search solves many graph problems in linear time; they received the 1986 Turing Award in part for that work.

Uses

Build tools such as make compile files after the files they depend on. Package managers install libraries in dependency order. Spreadsheets recalculate a cell after the cells its formula uses. Universities check that course prerequisites can be met, compilers order instructions, and data pipelines run each step after its inputs are ready. The Unix command tsort does a topological sort on its own.

Explore it

Open the app and press Step. The arrows say which node must come before which. With Kahn's algorithm, the number on each node counts its remaining incoming arrows, and free nodes are blue. With the DFS method, blue nodes are being visited and green ones are placed. The order grows in the row under the graph. Tick Add a cycle and watch both methods discover that no order exists.

Frequently asked questions

What does topological mean here?

The name comes from topology, the study of how things are connected rather than their exact shape. The order depends only on which nodes are connected by arrows, not on where they are drawn.

How do I find the cycle when there is no order?

The DFS method shows it directly: the edge to a node still being visited, together with the path of nodes being visited, is the cycle. Kahn's algorithm only tells you which nodes are stuck; a search among those finds the cycle.

Can I choose a particular order among the valid ones?

Yes. In Kahn's algorithm, when several nodes are free, pick the one you prefer, for example the smallest label or the most urgent task. Using a priority queue gives the order that comes first alphabetically.

How is topological sort used with shortest paths?

On a directed acyclic graph, relaxing the edges of each node in topological order finds all shortest paths from a start in a single pass, even with negative edges, faster than Dijkstra or Bellman–Ford.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Try topological sort