codaBack to Academy
graphs
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. It uses either DFS or Kahn's algorithm (BFS with in-degree tracking). It is essential for scheduling tasks with dependencies.
Use Cases
- •Task scheduling with dependency resolution
- •Build systems and compilation order
- •Course prerequisite planning
Complexity Analysis
| Metric | Best | Average | Worst |
|---|---|---|---|
| Time | O(V + E) | O(V + E) | O(V + E) |
| Space | O(V) | ||
Visualization
Implementation
Output
Click "Run Code" to see output...