Topological Sort
Topological Sort is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge (u → v), vertex u appears before vertex v in the ordering. It is only possible for DAGs — graphs with cycles cannot be topologically sorted. Topological sort is essential in task scheduling, build systems (e.g., Makefile dependency resolution), course prerequisite ordering, and instruction scheduling in compilers.
Topological Sort Algorithms Comparison
| Algorithm | Approach | Time Complexity | Space Complexity | Cycle Detection |
|---|---|---|---|---|
| Kahn's Algorithm | BFS-based, in-degree counting | O(V + E) | O(V) | Yes — detects if sort incomplete |
| DFS-based Sort | DFS post-order reversal | O(V + E) | O(V) | Yes — via back-edge detection |
| Both produce | Valid linear order of DAG | O(V + E) | O(V) | Equivalent in correctness |
| Applicable to | DAGs only | Linear in graph size | Vertex storage | Not valid for cyclic graphs |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Depth-First Search
Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking, using a stack (either explicit or via recursion) to track the path. It is fundamental in computer science for solving problems involving connected components, cycle detection, and pathfinding. DFS is widely used in topological sorting, maze generation, and solving puzzles like Sudoku.
Minimum Spanning Tree
A Minimum Spanning Tree (MST) of a connected, undirected, weighted graph is a spanning subgraph that connects all vertices with the minimum possible total edge weight, containing exactly V-1 edges for V vertices and no cycles. The MST is not necessarily unique if multiple edges have equal weights. MSTs are used in network design (telecom, power grids), cluster analysis, approximation algorithms for the Travelling Salesman Problem, and Euclidean geometry.
Dynamic Programming
Dynamic Programming (DP) is an algorithmic paradigm that solves complex problems by breaking them into overlapping subproblems, solving each subproblem only once, and storing results to avoid redundant computation (memoization or tabulation). It applies when a problem exhibits two key properties: optimal substructure (optimal solution contains optimal solutions to subproblems) and overlapping subproblems. DP is used in sequence alignment, shortest-path problems, knapsack optimization, and compiler design.
From Greek topos (place) and logos (study), giving "topology" — the mathematical study of properties preserved under continuous deformations. "Topological sort" was adopted in computer science in the 1960s to describe ordering vertices by their dependency structure. The algorithm was formalized in works by Arthur Kahn (1962) and others.