Topological Sort Resource

Topological Sort Resource - aloalgo

Topological sort orders vertices in a directed acyclic graph (DAG) so that for every edge u → v, u comes before v. It's used for dependency resolution: tasks, build systems, course prerequisites.

Process vertices with no incoming edges first. Remove them, update in-degrees, repeat.

Do a DFS, add nodes to result after processing all their dependencies. Reverse at the end.

Topological sort only works on DAGs. If there's a cycle, no valid ordering exists.

Classic interview problem: can you finish all courses given prerequisites?

Time: O(V + E) - visit each vertex and edge once
Space: O(V) for in-degree array and queue

Was this helpful?

Study plan All problems

Resources Cheat Sheet DSA Glossary

Topological Sort

Example

Kahn's Algorithm (BFS)

DFS-Based Approach

Cycle Detection

Course Schedule Problem

Finding Course Order

Complexity

Company

Practice

Learn