vault

Topological Sort

11 min read

Topological Sort

Topological sort produces a linear ordering of the vertices of a directed acyclic graph (DAG) such that for every edge (u, v), u comes before v in the ordering. Two algorithms compute it in O(V + E) time: Kahn’s algorithm (BFS-based, repeatedly removes in-degree-0 vertices) and the DFS-based algorithm (post-order traversal, then reverse). Topological sort is the algorithmic backbone of build systems, course scheduling, dependency resolution, package managers, and DAG-shortest-path problems. It also doubles as a cycle detector — a graph has a topological ordering iff it has no directed cycle.

1. Intuition — Wear Socks Before Shoes

You’re getting dressed. Each clothing item has prerequisites:

  • socks → shoes
  • underwear → pants
  • pants → belt
  • shirt → tie

What’s a valid order to put everything on? Many orderings work — socks, underwear, shirt, pants, belt, tie, shoes is fine; so is underwear, pants, shirt, socks, tie, belt, shoes. Any order that respects all “before” relationships is valid. That’s a topological sort.

What isn’t valid: shoes, socks (you can’t put shoes on before socks). What’s impossible: a circular requirement — if “shirt requires tie” and “tie requires shirt,” there’s no valid order. Topological sort signals impossibility by failing.

The two natural algorithms:

  • Kahn’s: “Find someone with no prerequisites. Put them on. Cross out their dependencies. Repeat.”
  • DFS-based: “Walk the dependency graph; once you’ve finished a vertex (and all its descendants), put it on the front of the to-do list.”

Both work, both are O(V+E), both are common interview answers. Kahn’s is conceptually simpler; DFS-based is shorter to code.

2. Tiny Worked Example

Course prerequisites:

  • Calc1 → Calc2
  • Calc1 → LinAlg
  • Calc2 → Calc3
  • LinAlg → Calc3
  • Programming → Algorithms
  • Calc2 → Algorithms

Graph:

Programming ──→ Algorithms
                    ↑
   Calc2 ──────────┘
     ↑
   Calc1
     ↓
   LinAlg ──→ Calc3
              ↑
   Calc2 ────┘

In-degrees: Programming=0, Calc1=0, Calc2=1, LinAlg=1, Calc3=2, Algorithms=2.

Kahn’s algorithm trace:

  • Start: queue = [Programming, Calc1] (the in-degree-0 vertices).
  • Pop Programming. Output: [Programming]. Decrement in-degree of Algorithms: 1.
  • Pop Calc1. Output: [Programming, Calc1]. Decrement in-degree of Calc2 (→ 0, enqueue) and LinAlg (→ 0, enqueue).
  • Pop Calc2. Output: [Programming, Calc1, Calc2]. Decrement Calc3 (→ 1) and Algorithms (→ 0, enqueue).
  • Pop LinAlg. Output: [Programming, Calc1, Calc2, LinAlg]. Decrement Calc3 (→ 0, enqueue).
  • Pop Algorithms. Output: … + Algorithms.
  • Pop Calc3. Output: … + Calc3.

Final order: Programming, Calc1, Calc2, LinAlg, Algorithms, Calc3. (Other orderings are equally valid.)

3. Kahn’s Algorithm (BFS-Based)

The intuition: at any point, a vertex with in-degree 0 has no remaining prerequisites and can come next.

kahn(graph):                                    # graph: dict u → list of v (directed edges)
    in_degree := map vertex → 0
    for each u in graph:
        for each v in graph[u]:
            in_degree[v] += 1
    queue := all vertices with in_degree 0
    output := empty list
    while queue is not empty:
        u := dequeue
        append u to output
        for each v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                enqueue v
    if length(output) < V:
        return None                              # cycle exists
    return output

Python:

from collections import deque, defaultdict
 
def kahn(graph, num_vertices):
    in_deg = defaultdict(int)
    for u in range(num_vertices):
        in_deg[u]                               # ensure key exists
    for u in graph:
        for v in graph[u]:
            in_deg[v] += 1
    q = deque(u for u in range(num_vertices) if in_deg[u] == 0)
    out = []
    while q:
        u = q.popleft()
        out.append(u)
        for v in graph.get(u, []):
            in_deg[v] -= 1
            if in_deg[v] == 0:
                q.append(v)
    if len(out) < num_vertices:
        return None                              # cycle
    return out

Cycle detection: if the final output list has fewer than V vertices, there’s a cycle (some vertex never had its in-degree reach 0).

4. DFS-Based Algorithm

Run DFS on the entire graph; when a vertex finishes (i.e., we return from its recursive call), prepend it to the output. Equivalently: post-order DFS, then reverse.

dfs_topo(graph):
    visited := set
    in_progress := set
    output := empty list
    for each u in graph:
        if u not in visited:
            if not dfs(u):
                return None                      # cycle
    return reverse(output)

dfs(u):
    if u in in_progress: return false             # back edge → cycle
    if u in visited: return true
    in_progress.add(u)
    for each v in graph[u]:
        if not dfs(v): return false
    in_progress.remove(u)
    visited.add(u)
    output.append(u)
    return true

Python:

def dfs_topo(graph, num_vertices):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * num_vertices
    out = []
    def dfs(u):
        color[u] = GRAY
        for v in graph.get(u, []):
            if color[v] == GRAY: return False    # back edge → cycle
            if color[v] == WHITE and not dfs(v): return False
        color[u] = BLACK
        out.append(u)
        return True
    for u in range(num_vertices):
        if color[u] == WHITE:
            if not dfs(u): return None
    return out[::-1]

Why post-order reverse works: when we finish a vertex u, every vertex reachable from u has already finished (we recursed into them first). So in the post-order list, every descendant appears before its ancestor. Reversing gives “ancestor before descendant” — the topological property.

5. Comparing the Two Algorithms

PropertyKahn’sDFS-based
Algorithm styleBFS / iterativeDFS / recursive
Cycle detection”Output size < V""Back edge found”
MemoryO(V + E) (queue + in_degree array)O(V) recursion stack + visited
Output orderingLexicographically natural with min-heapReverse of finish order — less predictable
Output multiple valid orders?Yes (depends on queue order)Yes (depends on neighbor order)
Stack overflow risk?No (iterative)Yes for deep DAGs (Python recursion limit)
Easier to add tie-breaking (e.g., lex-smallest order)Yes (use min-heap instead of queue)Harder

Pick Kahn’s when you want lex-smallest output, when stack overflow is a risk, or when iterative code is preferred. Pick DFS-based when the algorithm is simpler to express recursively (or when you’re already doing DFS for another reason, like SCC or cycle detection).

6. Lexicographically Smallest Topological Order

Replace Kahn’s queue with a min-heap: at each step, pop the smallest in-degree-0 vertex.

import heapq
 
def kahn_lex(graph, num_vertices):
    in_deg = [0] * num_vertices
    for u in graph:
        for v in graph[u]:
            in_deg[v] += 1
    heap = [u for u in range(num_vertices) if in_deg[u] == 0]
    heapq.heapify(heap)
    out = []
    while heap:
        u = heapq.heappop(heap)
        out.append(u)
        for v in graph.get(u, []):
            in_deg[v] -= 1
            if in_deg[v] == 0:
                heapq.heappush(heap, v)
    return out if len(out) == num_vertices else None

Time becomes O((V+E) log V) due to heap ops. The DFS-based variant doesn’t naturally give lex-smallest order — Kahn’s wins here.

7. Cycle Detection — Two Sides of the Same Coin

A directed graph has a topological order iff it has no directed cycle. Both algorithms naturally detect cycles:

  • Kahn’s: if some vertices never reach in-degree 0, they’re in a cycle (or downstream of one).
  • DFS-based: if DFS encounters an edge to a vertex currently in the recursion stack (a “back edge”), that’s a cycle.

Either approach gives O(V+E) cycle detection in directed graphs. For undirected graphs, use Union-Find or DFS with parent-tracking.

8. DAG Shortest/Longest Path via Topological Sort

For a weighted DAG, topological sort gives O(V+E) shortest (or longest) paths — better than Dijkstra’s O((V+E) log V) and works with negative edges (since DAGs can’t have negative cycles).

def dag_shortest_path(graph, num_vertices, source):
    """graph: dict u -> list of (v, w). DAG required."""
    topo = kahn(graph, num_vertices)
    if topo is None: return None                # cycle
    INF = float('inf')
    dist = [INF] * num_vertices
    dist[source] = 0
    for u in topo:
        if dist[u] == INF: continue
        for v, w in graph.get(u, []):
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

The trick: process vertices in topological order. When we get to u, all its predecessors have been processed, so dist[u] is final. Each edge is relaxed exactly once.

For longest path on DAG: same algorithm with > instead of <. Longest-path on a general graph is NP-hard; on a DAG it’s O(V+E).

9. Common Interview Problems

ProblemPattern
LC 207 — Course ScheduleKahn’s (BFS) or DFS cycle check
LC 210 — Course Schedule IITopological sort, output the order
LC 269 — Alien DictionaryBuild graph from char ordering, topo sort
LC 310 — Minimum Height TreesKahn-like “peel layers” approach
LC 444 — Sequence ReconstructionTopological sort with uniqueness check
LC 1136 — Parallel CoursesTopological sort with level / round counting
LC 2050 — Parallel Courses IIITopological sort + DAG longest-path
Build system / package manager dependency resolutionTopological sort
Spreadsheet formula evaluation orderTopological sort over cell-dependency graph

If a problem mentions “prerequisites,” “dependencies,” “build order,” or “schedule with constraints,” topological sort is on the shortlist.

10. Pitfalls

10.1 Cycle Misdiagnosed as Disconnected Graph

In Kahn’s, “fewer than V outputs” means a cycle exists. But what if the graph is disconnected — does that produce fewer outputs? No — every reachable vertex (from any in-degree-0 starting vertex) will be processed eventually. Disconnected components with their own in-degree-0 starts are handled fine. Only cycles produce the “stuck” condition.

10.2 Forgetting to Initialize In-Degree for Isolated Vertices

If your graph dict only has entries for vertices with outgoing edges, isolated vertices won’t appear in the in-degree map and won’t get enqueued. Initialize in_deg[v] = 0 for every vertex first.

10.3 Modifying Graph During DFS

Don’t decrement in-degree as you go in DFS-based topo sort — that’s Kahn’s pattern. Mixing the two confuses correctness.

10.4 Returning the Wrong Direction

DFS-based topo sort: post-order then reverse. Forgetting the reversal gives a backwards order (descendants before ancestors). Trace by hand on the smallest non-trivial example.

10.5 Trying to Top-Sort an Undirected Graph

Topological sort is for directed graphs. Applying it to undirected graphs is meaningless (every edge is a “cycle of length 2”). Read the problem carefully.

10.6 Stack Overflow on Deep DFS

A deep DAG (long chain) can blow Python’s recursion limit. Either sys.setrecursionlimit(N) or use iterative Kahn’s.

10.7 Multiple Valid Outputs Confusing Tests

A topological sort is not unique in general. If you compare your output to a “expected” output character-by-character, you’ll get false negatives. Test by verifying the output respects all edges, not by exact string match.

10.8 Counting “Number of Topological Sorts”

Often asked as a follow-up. P-complete in general (no efficient algorithm known). Don’t try to enumerate them all on big inputs.

11. Diagram — Kahn’s Layers

flowchart TD
  L0[Layer 0: in-degree-0 vertices<br/>start of topo order]
  L0 --> L1[Layer 1: vertices whose only in-edges<br/>came from Layer 0]
  L1 --> L2[Layer 2: vertices whose in-edges<br/>are from Layer 0 or 1]
  L2 --> Ln[...]
  Ln --> LK[Layer K: deepest vertices<br/>end of topo order]

What this diagram shows. Kahn’s algorithm processes vertices in layers: layer 0 is everything with no prerequisites, layer 1 is everything whose prerequisites are exclusively in layer 0, etc. The total count of layers is the longest path in the DAG — useful for problems like “minimum semesters to complete all courses” (LC 1136, LC 2050).

12. Why Topological Sort Is Universal in Build/Dep Systems

Every dependency-resolution system uses topological sort:

  • Make / Bazel / Ninja: build graph of (target → dependencies); execute targets in topo order.
  • Package managers (apt, npm, pip): install package after dependencies.
  • Spreadsheet calc engines: compute cells in dependency order.
  • Database query optimizers: plan operations in dependency order.
  • Module loaders: import modules in dependency order; circular imports are detected as cycles.
  • CI/CD pipelines: DAG of jobs; run in topo order with parallelization across independent branches.

Knowing topo sort is the prerequisite for designing any of these systems, which is why it’s so common in system-design interviews.

13. Variants

13.1 Parallel Topological Sort

Within Kahn’s, all vertices in the current “layer” can be processed in parallel. With P workers, total time becomes O((V+E) / P + longest_path).

13.2 Lexicographically Smallest

Use a min-heap instead of a queue (covered in §6).

13.3 Topological Sort with Tie-Breaking by Some Score

Use a heap keyed by the score. E.g., “order tasks by deadline among ready tasks.”

13.4 Online Topological Sort

Maintain a topological order as edges are added incrementally. Specialized algorithms (Pearce-Kelly, Marchetti-Spaccamela) achieve O(δ) amortized per edge insertion where δ is the number of vertices that must move.

14. Open Questions

  • How much can topological sort be parallelized in theory? PRAM O(log V) exists but is rarely implemented.
  • Is there a more cache-friendly variant for huge graphs? Active research; modern external-memory MST/topo-sort variants exist.

15. See Also

Graph View

Backlinks