Topological Sort

Why you need it

Many real problems are phrased as dependencies:

• •Course planning: “take Calculus I before Calculus II”
• •Build systems: “compile files before linking”
• •Data pipelines: “clean data before training”
• •Causal graphs: “causes precede effects”

A dependency is naturally modeled as a directed edge.

• •Write u -> v to mean: “u must happen before v” (u is a prerequisite of v).

If you want to execute everything, you need a single sequence of all tasks that respects every edge.

That is exactly what topological sorting provides.

Definition (with intuition)

Let G = (V, E) be a directed graph.

A topological ordering of G is a linear ordering of all vertices:

v₁, v₂, …, vₙ

such that for every directed edge u -> v in E, u appears before v in the ordering.

A topological sort is an algorithm that returns such an ordering.

Key intuition: edges point “forward in time.” Topological order is a timeline that never violates an arrow.

The DAG requirement: why cycles break everything

A topological ordering exists if and only if the graph is a DAG (Directed Acyclic Graph).

• •If there is a directed cycle:
• •A -> B -> C -> A

then A must come before B, B before C, and C before A. That last constraint contradicts the first two. No linear order can satisfy all.

• •If the graph is acyclic, you can always find at least one “starting” node with no prerequisites, place it first, remove it, and repeat.

This “starting node exists” fact is not just intuitive—it’s the engine behind Kahn’s algorithm.

Not unique—and that’s a feature

Topological orderings are often not unique.

Example:

• •Edges: A -> C, B -> C

Both A and B must precede C, but A and B can be swapped:

• •A, B, C
• •B, A, C

This reflects reality: when tasks are independent, you have scheduling freedom.

What topological sort does not guarantee

Topological sort ensures validity (dependency constraints), not:

• •minimal total time (that’s scheduling with durations and resources)
• •minimal number of steps (that’s different)
• •uniqueness

Think of it as producing a feasible plan, not necessarily the optimal one.

Why this approach works

If the graph is a DAG, there must be at least one vertex with indegree 0 (no incoming edges). Call these vertices sources.

Why must a source exist?

• •Suppose (for contradiction) every vertex has indegree ≥ 1.
• •Pick any vertex v₀. Since indegree ≥ 1, there exists v₁ with v₁ -> v₀.
• •Similarly, there exists v₂ with v₂ -> v₁, and so on.
• •Because the graph is finite, some vertex repeats, creating a directed cycle.
• •That contradicts acyclicity.

So in a DAG, at least one source exists. If you output a source first, you can safely remove it and continue. This yields a valid ordering.

Algorithm idea

Maintain:

• •indegree[v] = number of incoming edges to v
• •a queue (or stack) of all vertices with indegree 0

Repeatedly:

1. 1)pop a vertex u with indegree 0
2. 2)output u
3. 3)for each edge u -> v:

• •decrement indegree[v]
• •if indegree[v] becomes 0, push v

At the end:

• •if you output all vertices, success: you have a topological order
• •otherwise, the remaining vertices are in (or depend on) a directed cycle → no topo order exists

Walkthrough with a concrete graph

Consider tasks:

• •A -> D
• •B -> D
• •C -> E
• •D -> F
• •E -> F

Compute indegrees:

• •indegree[A]=0, indegree[B]=0, indegree[C]=0
• •indegree[D]=2 (A,B)
• •indegree[E]=1 (C)
• •indegree[F]=2 (D,E)

Initialize queue with A,B,C.

One possible run:

• •pop A → output A → D indegree: 2→1
• •pop B → output B → D indegree: 1→0 (push D)
• •pop C → output C → E indegree: 1→0 (push E)
• •pop D → output D → F indegree: 2→1
• •pop E → output E → F indegree: 1→0 (push F)
• •pop F → output F

Result: A, B, C, D, E, F

Another valid result might start with C, then A, etc. Kahn’s algorithm naturally allows multiple answers depending on how you choose among indegree-0 nodes.

Complexity and data structures

Let n = |V|, m = |E|.

• •Computing indegrees: O(m)
• •Each vertex enters/leaves the queue once: O(n)
• •Each edge processed once when its source is output: O(m)

Total: O(n + m) time and O(n + m) space (for adjacency list, indegrees, queue).

Cycle detection with Kahn’s algorithm

If there is a directed cycle, no vertex in that cycle can ever reach indegree 0 (within the subgraph induced by remaining vertices). So the queue empties early.

A reliable check:

• •If output_count < n ⇒ cycle exists ⇒ no topological ordering.

This is a practical benefit: Kahn’s algorithm is both a sorter and a cycle detector.

Queue vs stack vs priority queue

The container for indegree-0 vertices affects which valid ordering you get.

All produce valid topological orders as long as you always remove a vertex with indegree 0.

Why DFS can produce a valid ordering

You already know DFS as a traversal. For topological sort, the key observation is about finishing time.

During DFS, a node u “finishes” after exploring all outgoing edges u -> v and fully finishing those descendants v.

In a DAG, if there is an edge u -> v, then v must finish before u finishes (because DFS from u will (directly or indirectly) reach v, or v is explored in another DFS tree but still cannot create a back edge in a DAG).

So if we list nodes in decreasing finishing time, u will appear before v whenever u -> v.

That ordering is exactly a topological ordering.

The actual recipe

1. 1)Run DFS on the directed graph (starting from every unvisited vertex to cover disconnected parts).
2. 2)When a vertex u finishes, append it to a list (often called order).
3. 3)Reverse order at the end.

Equivalently: push u onto a stack at finish-time; popping the stack yields topo order.

Cycle detection via DFS colors (why it matters)

DFS-based topo sort is typically paired with cycle detection using a 3-state visitation scheme:

• •WHITE: unvisited
• •GRAY: in current recursion stack (actively exploring)
• •BLACK: finished

When exploring an edge u -> v:

• •if v is WHITE: recurse
• •if v is GRAY: you found a back edge, which implies a directed cycle ⇒ no topo order
• •if v is BLACK: ignore (already finished)

This is conceptually clean: a back edge means “u depends on something currently depending on u,” which is exactly the cycle contradiction.

Example (showing finishing order)

Edges:

• •1 -> 2
• •1 -> 3
• •3 -> 4

One DFS run:

• •start 1
• •go 2 (finish 2)
• •go 3
• •go 4 (finish 4)
• •finish 3
• •finish 1

Finish sequence (append at finish): [2, 4, 3, 1]

Reverse: [1, 3, 4, 2]

Check constraints:

• •1 before 2 ✓
• •1 before 3 ✓
• •3 before 4 ✓

Complexity

Same as Kahn’s algorithm:

• •DFS visits each vertex once, each edge once ⇒ O(n + m)
• •space: O(n + m) for adjacency plus O(n) recursion stack (or explicit stack)

Kahn vs DFS: when to choose which

If you’re thinking in terms of “what can I do next?”, Kahn’s algorithm matches that mental model.

If you’re already in DFS mode, reverse postorder is elegant and short.

1) Dependency resolution (build systems, packages, compilation)

Nodes are artifacts; edges encode prerequisites.

• •file.c -> file.o (compile)
• •file.o -> program.exe (link)

A topological order is a valid build order.

If a cycle exists (A depends on B depends on A), your build system should fail with a helpful cycle report.

2) Course planning / curriculum graphs

Nodes are courses; edges are prerequisites.

Topological sorting provides a feasible sequence of courses.

Often you also have constraints like “at most 4 courses per term.” Topological sort is still the backbone, but then you add batching/leveling (a scheduling layer).

3) Pipeline orchestration (ETL, ML training)

Data and model workflows are DAGs:

• •raw_data -> cleaned_data -> features -> model_train -> model_eval

Orchestrators (Airflow, Dagster, Prefect) effectively maintain the set of indegree-0 tasks that are ready to run—Kahn’s idea with extra machinery (retries, resources, time).

4) Dynamic programming on DAGs

A powerful pattern:

1. 1)Topologically sort vertices.
2. 2)Process vertices in that order to compute DP values.

Why it works: when you process v, all prerequisites u with u -> v have already been processed.

Example: longest path in a DAG.

Let dp[v] = length of longest path ending at v.

Then

• •dp[v] = max over (u -> v) of (dp[u] + 1)

Processing in topological order ensures dp[u] is ready when computing dp[v].

5) Causal graphs and “cause before effect”

In causal inference, DAGs represent directional assumptions (potential causal influence).

Topological ordering is not the full causal story, but it reinforces the key constraint: if u is a cause of v (directly or indirectly), u cannot come after v in a causal ordering.

6) From partial orders to linear extensions

A DAG defines a partial order: u ≤ v if there is a directed path u → … → v.

A topological ordering is a linear extension of that partial order.

This viewpoint helps explain non-uniqueness:

• •partial order leaves some pairs incomparable
• •topo sort chooses an arbitrary consistent order among incomparable elements

Practical note: validating an order

Given an ordering pos[·], you can verify it in O(n + m):

• •for every edge u -> v, check pos[u] < pos[v]

This is useful in testing: generate a topo order, then assert it respects all edges.

Summary

Topological sort is a “glue” primitive:

• •it converts a graph of constraints into a timeline
• •it’s efficient (O(n + m))
• •it naturally detects impossible constraints (cycles)

Once you see dependencies as edges, topo sort becomes the default tool.