Time Complexity
O(V + E)
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.
How it works (Kahn's Algorithm - BFS-based):
1. Compute the in-degree of each vertex
2. Add all vertices with in-degree 0 to a queue
3. While the queue is not empty:
a. Dequeue a vertex, add it to the result
b. For each outgoing edge, decrement the neighbor's in-degree
c. If a neighbor's in-degree becomes 0, enqueue it
4. If all vertices are processed, the result is a valid topological order
Time Complexity: O(V + E)
Space Complexity: O(V)
Applications:
- Task scheduling with dependencies
- Build systems (Make, Gradle)
- Course prerequisite planning
- Package dependency resolution
Topological Sort is only possible for DAGs (Directed Acyclic Graphs). If the graph has a cycle, no valid ordering exists.
Related algorithms
Frequently asked questions
- What is Topological Sort (Kahn's Algorithm)?
- 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.
- What is the complexity of Topological Sort (Kahn's Algorithm)?
- Time (average): O(V + E) · Space: O(V)
- Who is this Topological Sort (Kahn's Algorithm) visualizer for?
- The Topological Sort (Kahn's Algorithm) visualization targets advanced-level learners in the Graphs category. Useful for students, interview prep, and hands-on review.
- What algorithms are related to Topological Sort (Kahn's Algorithm)?
- In the same category (Graphs) you can explore: Breadth-First Search, Depth-First Search, Dijkstra's Algorithm. Each has an interactive visualization.