Topological Sort

Overview

What it is

A topological order lines up the nodes of a directed graph so that every edge goes from an earlier node to a later one. If course 5 is a prerequisite for course 2, then 5 comes before 2. Such an order exists exactly when the graph has no directed cycle, so the graph must be a DAG, a directed acyclic graph. Most graphs have several valid orders.

The running example has six courses and six prerequisite edges.

The in-degree of a node is the number of edges coming into it. A node with in-degree 0 has no prerequisites left and can go next.

• 0 — from 5, from 4 — 2
• 1 — from 4, from 3 — 2
• 2 — from 5 — 1
• 3 — from 2 — 1
• 4 — none — 0
• 5 — none — 0

Kahn's algorithm: peel the nodes with in-degree 0

Kahn's algorithm (Communications of the ACM, 1962) repeats one move. Take a node with in-degree 0, append it to the order, and remove its outgoing edges by lowering the in-degree of each neighbor. Any neighbor that drops to 0 becomes available. A queue holds the available nodes.

The trace below runs on the example, and nodes enter the queue in index order when they tie.

• start — 4, 5
• 1 — 4 — 0 to 1, 1 to 1 — 5 — 4
• 2 — 5 — 2 to 0, 0 to 0 — 2, 0 — 4, 5
• 3 — 2 — 3 to 0 — 0, 3 — 4, 5, 2
• 4 — 0 — none — 3 — 4, 5, 2, 0
• 5 — 3 — 1 to 0 — 1 — 4, 5, 2, 0, 3
• 6 — 1 — none — empty — 4, 5, 2, 0, 3, 1

Six nodes came out, so the order is complete: 4, 5, 2, 0, 3, 1. Check any edge, say 3 to 1: 3 is at position 5 and 1 at position 6, so it points forward.

DFS: reverse the finish order

The other method runs a depth-first search from every unvisited node and records each node when it finishes, that is, after all of its descendants are done. A node finishes only after everything it points to has finished, so the reverse of the finish order is a topological order.

• enter 0, finish 0 — 0
• enter 1, finish 1 — 0, 1
• enter 2, enter 3, finish 3 — 0, 1, 3
• finish 2 — 0, 1, 3, 2
• enter 4, finish 4 — 0, 1, 3, 2, 4
• enter 5, finish 5 — 0, 1, 3, 2, 4, 5

Reversed: 5, 4, 2, 3, 1, 0. That is a different valid order from Kahn's, which is normal. Record nodes on finish, never on entry: the entry order 0, 1, 2, 3, 4, 5 puts 0 before 5 and breaks the edge from 5 to 0.

To detect a cycle in DFS, give each node one of three states: not visited, in progress (on the current path), and done. Reaching a node that is in progress means the current path loops back to it.

Detecting a cycle

With Kahn's algorithm a cycle shows up as nodes that never reach in-degree 0. Take four nodes with edges 0 to 1, 1 to 2, 2 to 0 and 2 to 3.

• 0 — 1 (from 2) — no, 2 is never processed
• 1 — 1 (from 0) — no
• 2 — 1 (from 1) — no
• 3 — 1 (from 2) — no, even though 3 is not on the cycle

The output has 0 of 4 nodes. The rule is simple: if the order is shorter than the node count, there is a cycle, and Course Schedule answers false.

Levels: the fewest semesters

Process the queue one level at a time instead of one node at a time. Every node in a level has all its prerequisites in earlier levels, so the number of levels is the fewest rounds needed when each round can take any number of nodes, such as semesters, build stages or parallel batches.

• 1 — 4, 5 — no prerequisites
• 2 — 2, 0 — 5 is done, and 4 and 5 are done
• 3 — 3 — 2 is done
• 4 — 1 — 4 and 3 are done

The example needs four levels. The level of a node is the length of the longest path ending at it, plus one.

The same peeling in other problems

• Course Schedule, Course Schedule II — nodes with in-degree 0 — the queue is empty; a short order means a cycle
• Minimum Height Trees (undirected tree) — leaves, nodes with degree 1, level by level — one or two nodes remain: they are the centers
• Find Eventual Safe States — reverse every edge, then peel nodes with in-degree 0 in the reversed graph — the queue is empty; every node peeled is safe
• Sort Items by Groups Respecting Dependencies — groups in one topological order, items within each group in another — both orders are complete
• Alien Dictionary — letters with in-degree 0 in the graph built from adjacent words — all letters used, or a cycle means no valid alphabet

Find Eventual Safe States deserves a sentence. A node is safe when every path from it ends at a node with no outgoing edges. Reverse the edges: terminal nodes now have in-degree 0, and Kahn's algorithm reaches exactly the nodes whose every original edge leads to something safe. Nodes on or leading into a cycle are never reached.

Kahn or DFS, and the library

• Cycle detection — order shorter than V — in-progress node reached again
• Level or batch information — natural, one level per round — not directly
• Smallest order by index or name — replace the queue with a min-heap: O((V + E) log V) — not directly
• Recursion — none — depth up to V, so use an explicit stack for deep graphs
• Edge direction in code — needs in-degrees and an adjacency list — needs only the adjacency list

Python's standard library has graphlib.TopologicalSorter since 3.9. static_order() returns one valid order, prepare() raises CycleError when the graph has a cycle, and get_ready() with done() hands out nodes level by level for parallel work. Write Kahn's algorithm yourself and mention the library afterward.

What you will be able to do

• Build the adjacency list and in-degrees from a list of prerequisites without reversing the edge direction.
• Run Kahn's algorithm and DFS by hand on a small graph and explain why each produces a valid order.
• Detect a cycle with either method and say what the output looks like when one exists.
• Adapt the peeling idea to levels, undirected leaves, safe states and grouped items.

When to use it

• Ordering tasks with prerequisites: courses, build steps, package installs, spreadsheet cells
• Checking whether a set of dependencies is even possible (no cycle)
• Counting the fewest rounds when each round can run any number of independent tasks
• Finding nodes that cannot reach a cycle (safe states) by peeling the reversed graph
• Peeling leaves of an undirected tree to find its centers
• Any problem that says X must come before Y for many pairs

More Coding & DSA topics

• Shortest Path Algorithms
• Sliding Window
• Sorting Algorithms
• Stacks
• String DP
• Top K Elements
• Tree Traversals
• Trees
• Tries
• Two Heaps
• Two Pointers
• Union Find