What Is Topological Sort?
Topological Sort orders the vertices of a directed graph into a line so that for every edge u→v, u comes before v. It's how you turn "you must finish A before B" relationships — course prerequisites, task schedules, build dependencies — into a concrete order.
Precondition: the graph must be a DAG (directed acyclic graph). A cycle would demand "A before B and B before A" at once, making any order impossible.
The Core Is In-Degree
In-degree is "the number of edges coming into a vertex" = "the number of prerequisites not yet finished."
A vertex with in-degree 0 is a task you can do right now (no prerequisites). Doing it reduces the prerequisite count of the tasks it points to. That idea is Kahn's algorithm.
How It Works (Kahn's Algorithm)
Step 1. Compute the in-degree of every vertex.
Step 2. Push all in-degree-0 vertices into a queue.
Step 3. Pop one, append it to the result, and decrement the in-degree of each neighbor it points to. Push any neighbor that just hit 0.
Step 4. Repeat until the queue is empty. If the result holds every vertex, success; if the result is shorter than the vertex count, there's a cycle.
The AlgoNote visualization shows vertices becoming "ready" as their in-degree hits 0 and getting removed in turn.
Time and Space Complexity
| Complexity | |
|---|---|
| Time | O(V + E) |
| Space | O(V) |
Each vertex and edge is seen once, so it's O(V + E).
Walking Through an Example
Edges A→B, A→C, B→D, C→D:
- •in-degrees: A=0, B=1, C=1, D=2
- •process A → B, C reach 0 → enqueue
- •process B → D=1, process C → D=0 → enqueue
- •process D → result
A, B, C, D(or A, C, B, D)
Common Mistakes
- •Not detecting cycles: if the number of processed vertices is less than V, there's a cycle. Skipping this check reports a wrong partial result as the answer.
- •Assuming uniqueness: a topological order is usually not unique (when several in-degree-0 vertices exist). If the problem wants a specific order (e.g., lexicographic), use a priority queue.
- •Applying to undirected graphs: topological sort isn't defined without direction.
See It in Action on AlgoNote
Watch in-degree-0 vertices enter the queue and the in-degrees of downstream vertices shrink as each is processed, step by step on AlgoNote.