FoundationSource checked

Topological Sort

Orders the nodes of a directed acyclic graph so every prerequisite appears before its dependents.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Graph Traversal
Difficulty: Intermediate
Family: Dependency Ordering
Tier: Foundation
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 0
Relationships: 9
Code example: Ready
Visualization: Ready
Aliases: Toposort

Overview

Topological Sort processes a DAG by repeatedly choosing nodes whose incoming prerequisites are already satisfied, or by reversing DFS finishing order.

Core Concepts

DAGindegreedependency orderingcycle detection

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(V + E)

Average

O(V + E)

Worst

O(V + E)

Space

O(V)

When to Use

Use it for dependency ordering in DAGs.
Use it for build steps, course prerequisites, task scheduling, or compiler passes.
Use it when cycle detection should reject invalid dependency graphs.

When Not to Use

Avoid it when the graph may contain cycles unless cycle reporting is part of the implementation.
Avoid it for undirected graphs or arbitrary ordering problems without dependency edges.
Avoid assuming the output is unique; many DAGs have multiple valid orders.

What It Does

Orders dependency nodes
Detects when a dependency order is impossible

Use Cases

Build systems
Course prerequisites
Task dependency planning

Inputs

Directed acyclic graph

Outputs

Topological order
Cycle error if no valid order exists

Pseudocode

1.Count incoming edges for each node
2.Add nodes with no incoming edges to a queue
3.Remove a node and append it to the order
4.Reduce incoming counts for its outgoing neighbors
5.Add new zero-count nodes to the queue

Canonical Example

Input: edges = [compile -> test, test -> package]
Output: [compile, test, package]
Explanation: Each task appears before the tasks that depend on it.

Implementation Notes

Kahn's algorithm uses indegree counts and a queue of ready nodes.
DFS-based topological sort records nodes after exploring outgoing edges.
Define edge direction clearly before testing expected orders.

Common Pitfalls

Failing to detect cycles and returning a partial order as if it were valid.
Assuming there is only one correct topological order.
Interpreting edge direction inconsistently between prerequisites and dependents.