AdvancedO(V + E)· Level 06

Topological Sort

Linear ordering of a DAG — Kahn's & DFS approaches.

Intuition

If task B depends on task A, A must come before B in the schedule. Topological sort produces a valid linear order for any DAG. Kahn's algorithm peels off vertices with in-degree zero one at a time.

Step-by-step

1
Compute in-degree of every vertex.
2
Enqueue all vertices with in-degree 0.
3
Pop a vertex `u`, append to output, and decrement the in-degree of each neighbor.
4
If any neighbor reaches in-degree 0, enqueue it.
5
If the output has fewer than V vertices, the graph contains a cycle.

Pseudocode

pseudocode

KAHN(G):
  compute in_deg[v] for all v
  Q = all v with in_deg[v] == 0
  order = []
  while Q not empty:
    u = Q.dequeue()
    order.append(u)
    for v in G.neighbors(u):
      in_deg[v] -= 1
      if in_deg[v] == 0: Q.enqueue(v)
  if len(order) < |V|: cycle!

Implementation (Python)

python

from collections import deque, defaultdict

def topo_sort(graph):
    in_deg = defaultdict(int)
    for u in graph.adj:
        for v, _ in graph.neighbors(u):
            in_deg[v] += 1

    q = deque(u for u in graph.adj if in_deg[u] == 0)
    order = []

    while q:
        u = q.popleft()
        order.append(u)
        for v, _ in graph.neighbors(u):
            in_deg[v] -= 1
            if in_deg[v] == 0:
                q.append(v)

    if len(order) != len(graph.adj):
        raise ValueError("Graph has a cycle")
    return order

Real-world applications

Build systems (Make, Bazel) ordering compilation
Course scheduling with prerequisites
Spreadsheet formula evaluation