This algorithm requires a directed graph. Check Settings tab to configure.
Topological Sort
Linear ordering of vertices in directed acyclic graph
Time: O(V + E)
Space: O(V)
Use Case: Task scheduling, dependency resolution, build systems
Algorithm Execution
Select an algorithm and generate steps to begin visualization
About Topological Sort
Topological sort produces a linear ordering of the vertices of a directed acyclic graph (DAG) such that every edge points from an earlier vertex to a later one. It answers the question: in what order can tasks be performed when some tasks depend on others?
How it works
Two standard approaches exist. Kahn's algorithm repeatedly removes a vertex with no incoming edges, appending it to the order and decrementing the in-degree of its neighbors; a queue holds the current zero in-degree vertices. The DFS approach performs a depth-first search and outputs vertices in reverse order of their finish times. Both run in O(V + E). If vertices remain unprocessed (Kahn) or a back edge appears (DFS), the graph has a cycle and no valid order exists.
Applications
Topological ordering schedules build systems such as Make and Gradle, resolves package installation order, sequences university courses with prerequisites, orders spreadsheet cell evaluation, and schedules instruction execution in compilers. It is among the most common medium-difficulty interview questions on directed graphs.