Topological Sort

What Is Topological Sort?

A topological sort of a directed graph is a linear ordering of its vertices such that for every directed edge u → v, vertex u appears before vertex v in the ordering.

DAG:
     5 ──→ 0 ←── 4
     │             │
     └──→ 2 ──→ 3 ─┘
               │
               └──→ 1

Valid topological orderings (multiple exist):
  [5, 4, 2, 3, 1, 0]  ← one valid ordering
  [4, 5, 2, 3, 1, 0]  ← another valid ordering
  [5, 4, 0, 2, 3, 1]  ← another valid ordering

RULE: for every edge u→v, u must appear BEFORE v.

Verify [5, 4, 2, 3, 1, 0]:
  5→0: 5 is at index 0, 0 is at index 5. 0 < 5 ✓
  5→2: 5 is at index 0, 2 is at index 2. 0 < 2 ✓
  4→0: 4 is at index 1, 0 is at index 5. 1 < 5 ✓
  4→3: 4 is at index 1, 3 is at index 3. 1 < 3 ✓
  2→3: 2 is at index 2, 3 is at index 3. 2 < 3 ✓
  3→1: 3 is at index 3, 1 is at index 4. 3 < 4 ✓
  All edges satisfied ✓

Real-World Applications

COURSE SCHEDULING:
  Courses as vertices. Edge A→B means "take A before B".
  Topological sort gives a valid study order.

     Math101 ──→ Math201 ──→ Math301
     Math101 ──→ CS101   ──→ CS201
                 CS101   ──→ CS301

  Valid order: Math101, CS101, Math201, CS101, CS201, CS301, Math301

BUILD SYSTEMS (Make, Gradle, CMake):
  Files as vertices. Edge A→B means "compile A before B".
  Topological sort gives valid compilation order.

TASK SCHEDULING:
  Tasks as vertices. Edge A→B means "A must finish before B starts".
  Any topological order is a valid execution plan.

PACKAGE MANAGERS (npm, pip, apt):
  Packages as vertices. Edge A→B means "install A before B".
  Topological sort gives valid installation order.

Approach 1: DFS Post-Order Topological Sort

Use DFS. When a vertex finishes (all its descendants explored), push it onto a stack. Pop the stack at the end for topological order.

WHY POST-ORDER WORKS:
  For edge u→v: DFS explores v (and all its descendants) BEFORE
  finishing u. So v is pushed to stack BEFORE u.
  When we pop the stack, u comes out BEFORE v.
  u → v means u before v ✓

ALGORITHM:
  visited = [false] * V
  stack   = []

  for each unvisited vertex (outer loop):
    dfs(vertex, visited, stack)

  dfs(u, visited, stack):
    visited[u] = true
    for each neighbour v of u:
      if not visited[v]: dfs(v)
    stack.push(u)   ← push AFTER all descendants finished (post-order)

  topological order = stack popped top-to-bottom (or reversed)

Input:
6 6
5 0
5 2
4 0
4 1
2 3
3 1

Output:
Topological Order (DFS): [5, 4, 2, 3, 1, 0]

Dry Run: DFS Topological Sort

DAG:  5→0, 5→2, 4→0, 4→1, 2→3, 3→1

Adjacency list:
  0: []
  1: []
  2: [3]
  3: [1]
  4: [0, 1]
  5: [0, 2]

visited=[F,F,F,F,F,F], stack=[]

Outer loop i=0: not visited
  dfs(0): visited[0]=T, no neighbours → stack.push(0) → stack=[0]

Outer loop i=1: not visited
  dfs(1): visited[1]=T, no neighbours → stack.push(1) → stack=[0,1]

Outer loop i=2: not visited
  dfs(2): visited[2]=T
    nbr=3: not visited
      dfs(3): visited[3]=T
        nbr=1: visited → skip
        stack.push(3) → stack=[0,1,3]
    stack.push(2) → stack=[0,1,3,2]

Outer loop i=3: already visited → skip
Outer loop i=4: not visited
  dfs(4): visited[4]=T
    nbr=0: visited → skip
    nbr=1: visited → skip
    stack.push(4) → stack=[0,1,3,2,4]

Outer loop i=5: not visited
  dfs(5): visited[5]=T
    nbr=0: visited → skip
    nbr=2: visited → skip
    stack.push(5) → stack=[0,1,3,2,4,5]

Pop stack → [5, 4, 2, 3, 1, 0] ✓

Verify: every edge u→v has u before v:
  5→0: 5 at 0, 0 at 5 ✓
  5→2: 5 at 0, 2 at 2 ✓
  4→0: 4 at 1, 0 at 5 ✓
  4→1: 4 at 1, 1 at 4 ✓
  2→3: 2 at 2, 3 at 3 ✓
  3→1: 3 at 3, 1 at 4 ✓

Approach 2: Kahn's Algorithm (BFS / In-Degree Method)

Compute in-degrees. Start BFS with all zero-in-degree vertices. Process and remove vertices one by one, revealing new zero-in-degree vertices.

KAHN'S ALGORITHM:
  1. Compute in-degree of every vertex.
  2. Enqueue all vertices with in-degree = 0.
  3. While queue not empty:
       u = dequeue
       add u to result
       for each v in adj[u]:
         in-degree[v]--
         if in-degree[v] == 0: enqueue v
  4. If result.size == V: valid topological order.
     If result.size <  V: cycle exists (not a DAG).

INTUITION — PEELING LAYERS:
  Start with vertices that have no prerequisites (in-degree 0).
  After "doing" them, mark their outgoing edges as complete.
  New vertices become ready (in-degree drops to 0).
  Repeat — like peeling layers off an onion.

DAG: 5→0, 5→2, 4→0, 4→1, 2→3, 3→1

In-degrees:
  0:2  1:2  2:1  3:1  4:0  5:0

Queue initially: [4, 5]  (in-degree 0)

Process 4: result=[4]
  4→0: in-degree[0] = 2-1 = 1
  4→1: in-degree[1] = 2-1 = 1
  Queue: [5]

Process 5: result=[4,5]
  5→0: in-degree[0] = 1-1 = 0 → enqueue 0
  5→2: in-degree[2] = 1-1 = 0 → enqueue 2
  Queue: [0, 2]

Process 0: result=[4,5,0]
  0 has no outgoing edges.
  Queue: [2]

Process 2: result=[4,5,0,2]
  2→3: in-degree[3] = 1-1 = 0 → enqueue 3
  Queue: [3]

Process 3: result=[4,5,0,2,3]
  3→1: in-degree[1] = 1-1 = 0 → enqueue 1
  Queue: [1]

Process 1: result=[4,5,0,2,3,1]
  1 has no outgoing edges.
  Queue: []

result.size = 6 = V → No cycle! ✓
Topological order: [4, 5, 0, 2, 3, 1]

DAG Input:
6 6
5 0  5 2  4 0  4 1  2 3  3 1

Output:
Topological Order (Kahn's): [4, 5, 0, 2, 3, 1]

Cyclic Input:
3 3
0 1  1 2  2 0

Output:
Cycle detected — topological sort impossible!

Application: Course Schedule

Classic LeetCode problem — can you finish all courses given prerequisites?

Problem:
  n courses labeled 0 to n-1.
  prerequisites[i] = [a, b] means you must take b before a.
  Can you finish all courses?

Model as directed graph:
  Edge b → a (b must come before a)

Example:
  n=4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
  Edges: 0→1, 0→2, 1→3, 2→3

  In-degrees: 0:0, 1:1, 2:1, 3:2

  Kahn's:
    Queue=[0]
    Process 0: result=[0], reduce 1→0, 2→0 → queue=[1,2]
    Process 1: result=[0,1], reduce 3→1 → 3's in-degree=1
    Process 2: result=[0,1,2], reduce 3→0 → 3's in-degree=0 → queue=[3]
    Process 3: result=[0,1,2,3]
    result.size(4) == n(4) → CAN finish! ✓
    Valid order: [0, 1, 2, 3] or [0, 2, 1, 3]

Output:
Order: [0, 1, 2, 3]
Order: []   (impossible — cycle)

DFS vs Kahn's — Side by Side

SAME DAG: 5→0, 5→2, 4→0, 4→1, 2→3, 3→1

          DFS (post-order + reverse)      Kahn's (BFS in-degree)
  ─────────────────────────────────────────────────────────────
  Result  [5, 4, 2, 3, 1, 0]             [4, 5, 0, 2, 3, 1]
  Both are valid topological orderings ✓

COMPARISON:
  Feature                   DFS Approach       Kahn's Approach
  ─────────────────────────────────────────────────────────────
  Traversal style           Recursive DFS      Iterative BFS
  Data structure            Stack + call stack Queue
  Cycle detection           Separate check     Built-in (count < V)
  Result                    Push at DFS exit   Append at dequeue
  Order                     Reverse of push    Direct append
  Disconnected graphs       Outer loop needed  Outer loop NOT needed
  Recursion limit risk      Yes (deep graphs)  No (iterative)
  Memory                    O(V) stack         O(V) queue
  Preferred for             Path-based logic   Scheduling, cycle check
  Time complexity           O(V + E)           O(V + E)

WHEN TO CHOOSE DFS:
  ✓ Problem involves DFS path tracking simultaneously
  ✓ Need to identify back edges / strongly connected components
  ✓ Recursive solution is cleaner for the problem structure

WHEN TO CHOOSE KAHN'S:
  ✓ Cycle detection is also needed (count < V tells you)
  ✓ Avoiding recursion stack overflow (large graphs)
  ✓ Course scheduling, build systems — natural "prerequisite" model
  ✓ Want to process vertices at same level simultaneously

Complexity Summary

Both visit each vertex once and each edge once — O(V + E) total.

Space: O(V) for visited array, stack/queue, and in-degree array.

Common Mistakes

DFS: pushing vertex at entry (pre-order) instead of exit (post-order). If you push u when you first visit it, u goes to the stack before any of its dependencies. After reversal, u appears after its dependencies — backwards! Always push AFTER all recursive calls complete (post-order = DFS exit).

Kahn's: not building the graph correctly for course schedule problems. If prerequisites[i] = [a, b] means "take b before a", the edge must be b → a (prerequisite → dependent). Building a → b reverses the dependency and gives wrong results. The in-degree of the dependent (a) must be incremented, not the prerequisite (b).

Forgetting the outer loop in DFS for disconnected DAGs. DFS from one vertex only covers its reachable component. If the DAG has isolated vertices or separate components, the outer loop for i in range(V): if not visited[i]: dfs(i) is essential. Kahn's doesn't need this — its initial scan over all vertices handles all components.

Kahn's: not checking result.size() == V for cycle detection. If you skip this check and just return result, a cyclic graph silently returns a partial ordering of non-cycle vertices. Always verify the count equals V — if not, the missing vertices form a cycle and no valid topological order exists.

Multiple valid orderings: assuming uniqueness. Topological sort is not unique when multiple vertices have in-degree 0 simultaneously. If the problem requires a specific valid ordering (e.g., lexicographically smallest), use a min-heap (priority queue) instead of a regular queue in Kahn's.

Interview Questions

Q: Why does topological sort only work on DAGs?

Topological sort requires placing every edge u→v such that u comes before v. In a cycle A→B→C→A: A must come before B, B before C, and C before A — which requires A to come both before and after B simultaneously. This contradiction makes any linear ordering impossible. No valid topological order exists for cyclic directed graphs.

Q: How does Kahn's algorithm detect cycles as a side effect?

Kahn's processes vertices in topological order by always picking a vertex with in-degree 0. In a directed cycle, every cycle vertex always has at least one incoming edge from another cycle vertex — its in-degree never reaches 0 while cycle members remain. These vertices are never enqueued, never processed, never counted. After Kahn's completes, if processed count < V, those unprocessed vertices form a cycle.

Q: When does Kahn's produce a unique topological ordering?

Kahn's produces a unique ordering if and only if, at every step, exactly one vertex has in-degree 0 in the remaining unprocessed subgraph. This happens when the DAG is a Hamiltonian path — a single directed chain where each vertex has exactly one predecessor and one successor. If at any point multiple vertices have in-degree 0, they can be ordered in any way — the topological sort is non-unique.

Summary

Topological sort linearly orders vertices of a DAG such that every edge u→v has u before v. Only works on Directed Acyclic Graphs.

Two approaches — both O(V + E):

DFS (post-order):

1. ›Run DFS; push each vertex to stack AFTER all its descendants finish
2. ›Pop the stack — this gives topological order
3. ›Outer loop ensures all components are covered

Kahn's (BFS / in-degree):

1. ›Compute in-degree for all vertices
2. ›Enqueue all zero in-degree vertices
3. ›BFS: process, decrement neighbours' in-degrees, enqueue newly zeroed vertices
4. ›Check: if processed count < V → cycle exists

Classic problems: Course Schedule I/II, Alien Dictionary, Build Order, Task Dependencies.

In the next topic you will explore Shortest Paths — Dijkstra's algorithm for positive-weight graphs and Bellman-Ford for negative weights.