Topological Sort

Also Known As

TL;DR

Explanation

Topological sort is only possible on directed acyclic graphs (DAGs) — any cycle makes a valid ordering impossible. Two common algorithms: Kahn's algorithm uses in-degree counts and a queue (BFS-based), and DFS-based sort uses recursive post-order traversal. Both run in O(V + E). The result is not unique — many valid orderings may exist. Real-world applications are everywhere: package/dependency managers (Composer, npm) use it to determine installation order, build systems (Make, Gradle) use it for task scheduling, course prerequisite systems, and database migration runners rely on it to apply schema changes in the right order.

Diagram

flowchart LR
    subgraph DAG Input
        A --> B
        A --> C
        B --> D
        C --> D
        D --> E
    end
    subgraph Kahn Step-by-Step
        K1[Start: A has in-degree 0] --> K2[Process A<br/>reduce B and C]
        K2 --> K3[Process B and C<br/>reduce D]
        K3 --> K4[Process D<br/>reduce E]
        K4 --> K5[Process E<br/>done]
    end
    RESULT[Order: A - B - C - D - E]
style RESULT fill:#238636,color:#fff
style K1 fill:#1f6feb,color:#fff

Common Misconception

Why It Matters

Common Mistakes

• Not detecting cycles — silently returning a partial ordering when a cycle exists instead of throwing an error.
• Using topological sort on an undirected graph — the concept only applies to directed edges.
• Assuming the output order is unique — many valid orderings exist; tests should not depend on a specific one.
• Reinventing it manually with nested loops instead of using Kahn's or DFS — O(V²) instead of O(V+E).

Code Examples

// Naive: repeatedly scan for nodes with no unresolved deps — O(V²):
function topoNaive(array $deps): array {
    $resolved = [];
    while (count($resolved) < count($deps)) {
        $progress = false;
        foreach ($deps as $node => $nodeDeps) {
            if (!in_array($node, $resolved) &&
                empty(array_diff($nodeDeps, $resolved))) {
                $resolved[] = $node;
                $progress = true;
            }
        }
        if (!$progress) throw new RuntimeException('Cycle detected');
    }
    return $resolved;
}

// Kahn's algorithm — O(V+E) with cycle detection:
function topologicalSort(array $graph): array {
    $inDegree = array_fill_keys(array_keys($graph), 0);
    foreach ($graph as $neighbours) {
        foreach ($neighbours as $v) $inDegree[$v]++;
    }
    $queue = array_keys(array_filter($inDegree, fn($d) => $d === 0));
    $order = [];
    while ($queue) {
        $u = array_shift($queue);
        $order[] = $u;
        foreach ($graph[$u] as $v) {
            if (--$inDegree[$v] === 0) $queue[] = $v;
        }
    }
    if (count($order) !== count($graph)) {
        throw new RuntimeException('Graph has a cycle — topological sort impossible');
    }
    return $order;
}

// Usage: ['a' => ['b','c'], 'b' => ['d'], 'c' => ['d'], 'd' => []]
// Returns: ['a', 'b', 'c', 'd'] or ['a', 'c', 'b', 'd']

References

• ↗ https://en.wikipedia.org/wiki/Topological_sorting

Tags

Related Terms