Linear ordering of a DAG (Directed Acyclic Graph) where every edge u -> v has u before v. Cycle detection is implicit.

Data Flow (Kahn’s algorithm — BFS flavour)

graph:
   5 -> 3, 5 -> 7, 3 -> 7, 3 -> 8, 7 -> 8, 2 -> 4, 4 -> 9, 9 -> 8

indegrees: {5:0, 7:2, 3:2, 8:2, 2:0, 4:1, 9:1}

queue = nodes with indegree 0 = [5, 2]
pop 5 -> emit 5; reduce indeg(3)=1, indeg(7)=1
pop 2 -> emit 2; reduce indeg(4)=0  -> push 4
pop 4 -> emit 4; reduce indeg(9)=0  -> push 9
pop 9 -> emit 9; reduce indeg(8)=1
pop 3 -> emit 3; push 7, 8
pop 7 -> emit 7
pop 8 -> emit 8

topo order: 5 2 4 9 3 7 8

When to use

• Course / job scheduling with prerequisites.
• Build dependency resolution.
• “Can all tasks be completed?” — if topo length < nodes, there is a cycle.

Code (Kahn)

from collections import deque, defaultdict
 
def topo(graph, n):
    indeg = [0] * n
    for u in graph:
        for v in graph[u]:
            indeg[v] += 1
    q = deque([i for i in range(n) if indeg[i] == 0])
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return order if len(order) == n else []   # empty => cycle

Pitfalls

• Confusing indegree with outdegree direction.
• Forgetting the cycle check.

Analogy

Compiling a project: libs must be built before binaries that link them. Topo-sort produces the build order.

Interview tip: If a problem refers to prerequisites, dependencies, order of completion — topo sort.