Topological sort — DFS-based, Kahn's algorithm (BFS-based)

WHAT is a topological sort?

WHY does a cycle break it? If $a \to b \to c \to a$, then $a$ must come before $b$, $b$ before $c$, and $c$ before $a$. That forces $a$ before $a$ — impossible. So cycles ⇒ no topological order.

WHY two algorithms?

Both solve the same problem but think differently:

Both run in $O(V+E)$.

Algorithm 1 — DFS-based

HOW it works (derivation from first principles)

Claim: If we reverse the order in which DFS finishes vertices, every edge points forward.

Take any edge $u \to v$. When DFS first touches $u$, consider $v$'s state:

• $v$ unvisited: DFS will explore $v$ as a descendant of $u$, so $v$ finishes before $u$. ✅ ($u$ finishes later ⇒ $u$ earlier in reversed order)
• $v$ already finished: then $v$ finished before $u$ even started. ✅
• $v$ in progress (gray, on the stack): this means there's a path $v \rightsquigarrow u$ already, plus edge $u\to v$ = a cycle. Not allowed in a DAG. ❌ blocked.

In every valid (DAG) case, $u$ finishes after $v$, so in the reversed finish list $u$ precedes $v$. Edge points forward. ∎

function topoDFS(G):
    visited = {}, finished = []
    for each vertex u in V:
        if u not visited: dfs(u)
    return reverse(finished)

function dfs(u):
    mark u visited (GRAY)
    for each edge u -> v:
        if v GRAY:  report CYCLE   # back edge
        if v not visited: dfs(v)
    mark u BLACK
    finished.append(u)             # append on FINISH

Algorithm 2 — Kahn's Algorithm (BFS-based)

HOW it works (derivation)

Define $\text{indeg}(v)$ = number of edges pointing into $v$.

1. A DAG always has at least one vertex with indegree 0 (else follow incoming edges backward forever ⇒ a repeat ⇒ cycle). So we can always start.
2. Emitting a 0-indegree vertex and deleting its out-edges keeps the rest a DAG. By induction the whole graph empties out.
3. Every edge points forward: when we emit $u$, all of $u$'s prerequisites are already emitted; the edge $u\to v$ decrements $\text{indeg}(v)$, so $v$ is emitted strictly later. ✅

function kahn(G):
    compute indeg[v] for all v
    Q = queue of all v with indeg[v] == 0
    order = []
    while Q not empty:
        u = Q.pop()
        order.append(u)
        for each edge u -> v:
            indeg[v] -= 1
            if indeg[v] == 0: Q.push(v)
    if len(order) < |V|: report CYCLE   # leftover nodes stuck in a cycle
    return order

Worked Example (same graph, both methods)

Graph edges: 5→0, 5→2, 4→0, 4→1, 2→3, 3→1 Vertices: 0 1 2 3 4 5

Kahn's walk-through

Indegrees: 0:2, 1:2, 2:1, 3:1, 4:0, 5:0

Order: 4 5 0 2 3 1 — Why this step? We always pulled an indegree-0 node, guaranteeing every prerequisite was already out. 6 emitted = |V| ⇒ valid DAG.

DFS walk-through (start at 5, then 4)

• dfs(5)→dfs(0) finish 0 →dfs(2)→dfs(3)→dfs(1) finish 1, finish 3, finish 2, finish 5
• dfs(4): 0,1 done → finish 4
• finished list = [0,1,3,2,5,4]
• Reverse = 4 5 2 3 1 0

Why this step? We append each node only after its descendants finished, so reversing puts roots first. (Note: different valid order from Kahn — both correct!)

Common Mistakes

Active Recall

Connections

• Depth-First Search (DFS) — DFS-topo is just DFS + finish-time ordering.
• Breadth-First Search (BFS) — Kahn's is BFS driven by indegree.
• Directed Acyclic Graph (DAG) — the precondition for any topo order.
• Cycle Detection in Directed Graphs — both algorithms detect cycles as a byproduct.
• Course Schedule Problem — classic application of topological sort.
• Shortest Path in DAG — relax edges in topological order for $O(V+E)$ shortest paths.
• Strongly Connected Components — Kosaraju uses DFS finish ordering similarly.

Concept Map

Hinglish (regional understanding)