Topological Sorting
Ordering technique for directed acyclic graphs
Topological sorting is an algorithmic technique that produces a linear ordering of the vertices of a directed acyclic graph (DAG) such that for every directed edge from vertex u to vertex v, u appears before v in the ordering.
Definition
Topological sorting is an algorithmic technique that produces a linear ordering of the vertices of a directed acyclic graph (DAG) such that for every directed edge from vertex u to vertex v, u appears before v in the ordering.
Overview
Topological sorting only applies to directed acyclic graphs, since a cycle would make a consistent linear ordering impossible (any two vertices on the cycle would each need to precede the other). The two most common approaches are Kahn's algorithm, which repeatedly removes vertices with zero in-degree (no incoming edges) and adds them to the output while decrementing the in-degree of their neighbors, and a depth-first-search-based approach, which appends each vertex to the front of the result list once all of its descendants have been fully explored. Both approaches run in O(V + E) time, linear in the size of the graph. A given DAG can have multiple valid topological orderings unless the graph's structure fully constrains the order (a Hamiltonian path through the DAG), so topological sort produces one valid ordering among potentially many, not a unique canonical one. If the input graph contains a cycle, most implementations detect this condition and report that no valid topological ordering exists, which doubles as a general cycle-detection technique for directed graphs. Topological sorting underlies many practical systems: build tools and package managers use it to determine a valid compilation or installation order from a dependency graph; task schedulers use it to sequence jobs with prerequisites; spreadsheet applications use it to determine the order in which to recalculate formula cells; and course-scheduling systems use it to sequence classes given prerequisite constraints. It is also a foundational subroutine in more advanced graph algorithms, including certain shortest-path algorithms on DAGs and critical-path analysis in project scheduling.
Key Concepts
- Produces a linear vertex ordering consistent with all directed edges
- Only defined for directed acyclic graphs (DAGs)
- Commonly implemented via Kahn's algorithm (in-degree removal) or DFS
- Runs in O(V + E) linear time in the number of vertices and edges
- Multiple valid orderings can exist for the same graph
- Doubles as a cycle-detection technique for directed graphs
- Foundational for dependency resolution and build-order computation
- Basis for shortest-path computation and critical-path analysis on DAGs