Topological Sort

Topological sort orders nodes so dependencies come first.

Example: course prerequisites

graph = {
  "A": ["C"],
  "B": ["C"],
  "C": ["D"],
  "D": []
}

Kahn's algorithm

from collections import deque, defaultdict

def topo(g):
    indeg = defaultdict(int)
    for u in g:
        for v in g[u]:
            indeg[v] += 1

    q = deque([u for u in g if indeg[u] == 0])
    order = []

    while q:
        u = q.popleft()
        order.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order

print(topo(graph))

Graph

flowchart LR
  A --> C
  B --> C
  C --> D

Remember

• only for DAG (no cycles)
• used in scheduling and builds