Topological Sort
Subject: Computer and Technology noun /ˌtɑː.pəˈlɑː.dʒɪ.kəl ˈsɔːrt/ 1 definition
- graph-algorithms
- graph-theory
- dependency-resolution
- computer-science
-
Definition (noun)
Entry #55 · UpdatedA Topological Sort (also called a topological ordering) is a linear sequence of all vertices in a directed graph such that for every directed edge from vertex
uto vertexv,uappears beforev. Because a directed cycle makes any valid predecessor ordering impossible, a topological sort exists if and only if the graph is a Directed Acyclic Graph (DAG), and multiple valid orderings can exist whenever independent vertices lack a connecting dependency path. It serves as a core primitive in computer science for dependency resolution, build orchestration, task scheduling, and dataflow evaluation where prerequisite constraints must be satisfied.Common Forms
Kahn's Algorithm: Tracks each vertex's in-degree (incoming edge count), repeatedly dequeues zero-in-degree vertices into the sorted output, and decrements their neighbors' counts in O(V + E) time while detecting cycles if unvisited vertices remain.
Depth-First Search (DFS) Post-Order: Recursively explores outgoing neighbors in O(V + E) time and prepends each vertex to the final sequence once all of its descendants finish, flagging a cycle if an active ancestor is revisited.
Lexicographical Topological Sort: Replaces Kahn's standard queue with a min-heap (priority queue) to always select the smallest available zero-in-degree vertex next, yielding a unique deterministic ordering in O(V log V + E) time.
Parallel Level-Order Topological Sort: Batches all current zero-in-degree vertices into successive execution waves so build runners and workflow engines can run independent tasks within each layer concurrently.
Example
When a build tool compiles an
apppackage whoseauth-libandhttp-clientdependencies both importcrypto-core, it constructs a directed graph with edges pointing from each prerequisite to its dependents. Running Kahn's algorithm produces a valid topological sort such ascrypto-core,auth-lib,http-client,app, guaranteeing thatcrypto-corebuilds before any downstream package and halting with an error if a circular dependency creates a cycle.