Topological Sort Recap: Two Ways to Put Dependencies in Order

In-degrees and a queue, or reversed finishing times: both are O(V + E), both find cycles, and neither has one answer.

Topological Sort covered how to order the vertices of a directed graph so that every edge points forwards, by two methods that each run in O(V + E), and how each method tells you when no order exists. The table names each idea and the card that holds it.

What the topic established, and which card it was on
The idea	Where
An order exists exactly when the directed graph has no cycle	Topological Sort: Ordering Tasks So Every Edge Points Forwards
Output a vertex once its in-degree reaches 0, then lower its neighbours' counts	Trace Kahn's Algorithm With In-Degrees and a Queue of Ready Tasks
A graph usually has many valid orders; check the property, not one answer	Expecting One Correct Topological Order
Kahn's algorithm with a cycle check in three languages	Kahn's Algorithm in Python, Java and TypeScript
Fewer vertices output than the graph has means a cycle among those left	Detecting a Cycle by Counting the Output
Depth-first finishing order, reversed, is a topological order	Topological Order From Depth-First Finishing Times
Scheduling jobs with dependencies, and spotting a dependency loop	Practice: Scheduling the Jobs of a Kitchen Refit

The two methods meet the same graph from opposite ends. Kahn's algorithm starts with the vertices nothing depends on and works forwards; depth-first search finishes the vertices that depend on nothing further first and works backwards, which is why its list has to be reversed. On the topic's graph they gave C D A B E F and D C B E A F, and both point all six edges forwards.

Choose Kahn's algorithm when the graph is large or deep, because it needs no recursion, and when the count of tasks left is useful to report. Choose depth-first search when the code already walks the graph that way, or when the order is needed for each vertex as it finishes.

Topological sort, by method

Kahn's algorithm: O(V + E) time, O(V) space; cycle when the output is shorter than V
Depth-first search: O(V + E) time, O(V) space; cycle when an edge reaches a grey vertex
Valid orders: Usually many; 12 of the 720 orders of the topic's six vertices

Every edge in this topic cost the same, so the only question was which comes first. When edges carry weights, such as distances or travel times, the question becomes how far, and Shortest Paths, the next topic, answers it, using a topological order for one of its cases.

← → move through sections and cards