Topological Sort
Topological Sort produces a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u→v, vertex u comes before v in the ordering. This is essential for scheduling tasks with dependencies, resolving symbol dependencies in compilers, and determining build order in project management.
Visualization
Interactive visualization for Topological Sort
Topological Sort (DFS)
• Time: O(V + E)
• Linear ordering of vertices in DAG
• Used in task scheduling, build systems
Interactive visualization with step-by-step execution
Implementation
1function topologicalSort(graph: Map<number, number[]>): number[] {
2 const visited = new Set<number>();
3 const result: number[] = [];
4
5 function dfs(node: number): void {
6 if (visited.has(node)) return;
7 visited.add(node);
8
9 const neighbors = graph.get(node) || [];
10 for (const neighbor of neighbors) {
11 dfs(neighbor);
12 }
13
14 result.unshift(node);
15 }
16
17 for (const node of graph.keys()) {
18 dfs(node);
19 }
20
21 return result;
22}Deep Dive
Theoretical Foundation
Topological Sort only works on Directed Acyclic Graphs (DAGs) - graphs with directed edges and no cycles. There are two main approaches: DFS-based (depth-first search with stack) and Kahn's algorithm (BFS-based using in-degrees). The DFS approach visits all vertices, performing DFS from each unvisited vertex, and pushes vertices to a stack after exploring all descendants. The result is obtained by popping from the stack. Kahn's algorithm maintains a queue of vertices with in-degree 0, repeatedly removing them and updating neighbors' in-degrees. If a cycle exists, topological sort is impossible. The algorithm has applications in build systems (make, gradle), course prerequisite chains, task scheduling, and compiler symbol resolution.
Complexity
Time
O(V + E)
O(V + E)
O(V + E)
Space
O(V)
Applications
Industry Use
Build systems (Make, Gradle, Maven) - compile order
Course prerequisite scheduling in universities
Task scheduling with dependencies in project management
Package manager dependency resolution (npm, pip, apt)
Compiler symbol resolution and linking
Spreadsheet formula evaluation order
Event scheduling in simulations
Version control merge operations
Data pipeline execution order
Use Cases
Related Algorithms
Depth-First Search (DFS)
Graph traversal exploring as deep as possible before backtracking. DFS is a fundamental algorithm that uses a stack (either implicitly through recursion or explicitly) to explore graph vertices. It's essential for cycle detection, topological sorting, and pathfinding problems.
Breadth-First Search (BFS)
Level-by-level graph traversal guaranteeing shortest paths in unweighted graphs. BFS uses a queue to explore vertices level by level, making it optimal for finding shortest paths and solving problems that require exploring nearest neighbors first.
Dijkstra's Algorithm
Finds shortest path from source to all vertices in weighted graph with non-negative edges. Uses greedy approach with priority queue.
Floyd-Warshall Algorithm
Floyd-Warshall is an all-pairs shortest path algorithm that finds shortest distances between every pair of vertices in a weighted graph. Unlike Dijkstra (single-source), it computes shortest paths from all vertices to all other vertices simultaneously. The algorithm can handle negative edge weights but not negative cycles. Developed independently by Robert Floyd, Bernard Roy, and Stephen Warshall in the early 1960s.