Chapter 79

Topological Sort

A topological order of a DAG is an ordering where for every edge u→v, u comes before v. It's the foundation for DAG shortest paths, dependency resolution, and scheduling problems.

Kahn's Algorithm (BFS-based)

Track in-degree of each node. Repeatedly pick nodes with in-degree 0, remove them, and decrement in-degree of their neighbours.

C++ — Kahn's algorithm

vector topological_sort(vector>& adj) {
    int V = adj.size();
    vector in_deg(V, 0);
    for (int u = 0; u < V; u++)
        for (int v : adj[u]) in_deg[v]++;

    queue q;
    for (int i = 0; i < V; i++)
        if (in_deg[i] == 0) q.push(i);

    vector order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u])
            if (--in_deg[v] == 0) q.push(v);
    }

    if (order.size() != V) return {};  // cycle detected
    return order;
}

// O(V+E) — also detects cycles

Rust — Kahn's algorithm

fn topological_sort(adj: &[Vec]) -> Option> {
    let v = adj.len();
    let mut in_deg = vec![0; v];
    for u in 0..v {
        for &v in &adj[u] { in_deg[v] += 1; }
    }
    let mut q: VecDeque = (0..v).filter(|i| in_deg[*i] == 0).collect();
    let mut order = Vec::new();
    while let Some(u) = q.pop_front() {
        order.push(u);
        for &v in &adj[u] {
            in_deg[v] -= 1;
            if in_deg[v] == 0 { q.push_back(v); }
        }
    }
    if order.len() == v { Some(order) } else { None }
}

Key Takeaways

→Topological sort = linear ordering respecting edge direction.
→Kahn's algorithm: O(V+E), also detects cycles (order.size() != V).