Topological Sorting

Graph Theory · Axiom Academy

Linear ordering of vertices in directed acyclic graphs preserving dependency relationships 1. What is a Topological Ordering? A topological ordering of a directed graph is a linear arrangement of its vertices such that for every directed edge u→v, vertex u appears before vertex v in the sequence. For a directed graph G = (V, E), a topological ordering is a bijection f: V → 1, 2, ..., |V| such that: If (u, v) ∈ E, then f(u) < f(v) Course prerequisites: take courses in valid order Build systems: compile dependencies before dependents Task scheduling: complete prerequisites before dependent tasks Formula evaluation: compute values in dependency order Topological orderings exist if and only if the graph is a directed acyclic graph (DAG). This is not a limitation of our algorithms—it's a fundamental impossibility. Detecting Cycles: Both topological sort algorithms automatically detect cycles: Kahn's algorithm: If it doesn't process all vertices, a cycle exists DFS-based: If we encounter a back edge, a cycle exists Kahn's algorithm builds the topological ordering by repeatedly removing source vertices —vertices with no incoming edges. This greedy approach mirrors the intuition of "do what you can do now." Compute in-degree (number of incoming edges) for each vertex Initialize queue with all vertices having in-degree 0 While queue is not empty: Remove vertex u from queue and add to ordering For each neighbor v of u, decrease in-degree[v] If in-degree[v] becomes 0, add v to queue

This is the written version of the interactive lesson above. See the full Graph Theory course.