Skip to main content
Definition Website Computer and Technology

Topological Sort

Subject: Computer and Technology noun /ˌtɑː.pəˈlɑː.dʒɪ.kəl ˈsɔːrt/ 1 definition

  1. Definition (noun)

    Entry #55 · Updated

    A 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 u to vertex v, u appears before v. 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 app package whose auth-lib and http-client dependencies both import crypto-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 as crypto-core, auth-lib, http-client, app, guaranteeing that crypto-core builds before any downstream package and halting with an error if a circular dependency creates a cycle.