Directed Acyclic Graphs (DAGs): Kahn's Indegree Queue vs DFS Post-Order Reversal

Mathematical Duality: Source Peeling vs. Finish-Time Ordering

A directed graph $G = (V, E)$ admits a topological ordering if and only if $G$ is a DAG (contains no directed cycles). Both standard algorithms exploit complementary structural invariants of DAGs.

1. Kahn's Algorithm (1962): Indegree Peeling & Cycle Detection

Every non-empty finite DAG has at least one vertex with $\text{indegree}(u) = 0$ (otherwise walking backward along incoming edges would repeat a vertex in $\le |V|$ steps, forming a cycle). Kahn's algorithm maintains an array $\text{in}[0 \dots V-1]$ and a ready queue $Q$ of all vertices with $\text{in}[u] == 0$:

1. Pop $u$ from $Q$ and append $u$ to the topological order.
2. For each outgoing edge $(u, v)$, decrement $\text{in}[v]$. If $\text{in}[v]$ reaches $0$, push $v$ into $Q$.
3. Built-in Cycle Verification: If the loop terminates and the output list has fewer than $|V|$ vertices, the remaining vertices with $\text{in}[w] > 0$ contain at least one directed cycle (and everything reachable only from those cycles).

2. Lexicographically Smallest Topological Sort & Parallel Layering

Kahn's algorithm offers two capabilities that DFS post-order reversal cannot match directly:

• Lexicographically Smallest Topological Order: Replace the FIFO queue $Q$ in Kahn's algorithm with a min-heap (std::priority_queue<int, vector<int>, greater<int>>). At every step, among all currently unconstrained tasks ($ ext{in}[u] = 0$), picking the minimum index $u$ greedily produces the lexicographically smallest valid topological sequence in $O((V + E) \log V)$. (Note: sorting adjacency lists in DFS does not produce the lexicographically smallest topological sort!).
• Parallel Execution Waves (Level-by-Level Kahn): Processing all current zero-indegree vertices in batch waves yields the minimum number of parallel stages needed to execute a task graph with infinite processors—equal to the longest path in the DAG.

Complexity Matrix

Production Implementation: Zero-Allocation In-Place Kahn's Algorithm

#include <vector>
#include <queue>

// Returns topological order of size V, or an empty vector if G contains a directed cycle.
std::vector<int> topologicalSortKahn(int n, const std::vector<std::vector<int>>& adj) {
    std::vector<int> indegree(n, 0);
    for (int u = 0; u < n; ++u) {
        for (int v : adj[u]) {
            ++indegree[v];
        }
    }

    // Use the output vector itself as the FIFO queue (zero secondary queue allocation)
    std::vector<int> order;
    order.reserve(n);
    for (int u = 0; u < n; ++u) {
        if (indegree[u] == 0) {
            order.push_back(u);
        }
    }

    for (size_t readIdx = 0; readIdx < order.size(); ++readIdx) {
        int u = order[readIdx];
        for (int v : adj[u]) {
            if (--indegree[v] == 0) {
                order.push_back(v);
            }
        }
    }

    if (static_cast<int>(order.size()) != n) {
        return {}; // Directed cycle exists
    }
    return order;
}