Topological Sort

Table of Contents +

Think about your college courses. You can’t take Data Structures before you finish Programming Basics. Some courses must come before others. Now imagine you have a long list of courses and these “must come first” rules. In what order do you take them so you never break a rule? That ordering is exactly what topological sort gives you.

🎯 What Problem Are We Solving?

You have a bunch of tasks. Some tasks depend on other tasks. So task A must finish before task B can start. The hard part is finding a safe order to do everything. You never want to start a task before its dependencies are done.

This shows up everywhere:

  • Course prerequisites. Finish Maths I before Maths II.
  • Build systems. Compile the library before the app that uses it.
  • Project tasks. Lay the foundation before you build the walls.

Topological sort takes these dependencies and gives you one valid order. Every task comes after the tasks it depends on. In graph words, it orders the vertices of a directed graph so that every edge points from an earlier vertex to a later one.

📚 The Graph Behind It

We model this with a directed graph. Each task is a vertex. Each “A must come before B” rule is an arrow from A to B.

There is one important rule here. The graph must have no cycles. Say A needs B, and B needs A. Then neither one can ever go first. That is a deadlock. A directed graph with no cycles is called a DAG, short for Directed Acyclic Graph. Topological sort only works on a DAG.

Here is a small dependency graph. Read each arrow as “must come before”.

A: Basics

C: DSA

B: Maths

D: Algorithms

E: Databases

A and B have no arrows coming in. So they can go first. C needs both A and B done. D and E need C done. A valid order is A, B, C, D, E. Notice that B, A, C, E, D also works. Topological sort gives one valid order. It is not the only one.

Note

A graph can have more than one correct topological order. Any order that respects all the arrows counts as correct.

🧠 Kahn’s Algorithm: The Idea

The trick we’ll use is called Kahn’s algorithm. The idea is simple. It matches how you’d think about this in real life.

First, find any task with nothing pointing into it. That task has no pending dependencies. So it’s safe to do now. Do it, remove it, and that frees up the tasks that were waiting on it. Repeat until everything is done.

To track “nothing pointing into it” we use the in-degree of a vertex. In-degree is just the count of arrows coming into that vertex. A vertex with in-degree 0 has no dependencies left.

Here’s the plan in points:

  • Count the in-degree of every vertex.
  • Put every vertex with in-degree 0 into a queue. These are ready to go.
  • Take a vertex out of the queue. Add it to the answer.
  • For each vertex it points to, lower that neighbour’s in-degree by 1. If a neighbour’s in-degree drops to 0, push it into the queue.
  • Keep going until the queue is empty.

One more thing. Suppose we finish and our answer has fewer vertices than the graph. That means some vertices never reached in-degree 0. They were stuck in a cycle. So this same algorithm also tells us if the graph is not a DAG.

🪜 Steps to Do a Topological Sort

Let’s write the exact steps before we write code.

  1. Build the graph as an adjacency list and compute the in-degree of each vertex.
  2. Create an empty queue. Push every vertex whose in-degree is 0.
  3. Create an empty list called order for the result.
  4. While the queue is not empty, remove a vertex u from the front and append it to order.
  5. For each neighbour v of u, subtract 1 from the in-degree of v. If it becomes 0, push v into the queue.
  6. After the loop, check the size of order. If it has every vertex, it is a valid topological order. If it has fewer, the graph had a cycle.

Now let’s see it in all five languages. We’ll use the same graph from above, with vertices numbered 0 to 4 (A=0, B=1, C=2, D=3, E=4).

topological_sort.py
from collections import deque


# Kahn's algorithm using in-degree and a queue
def topological_sort(adj, n):
    indegree = [0] * n


    # Step 1: count in-degree for every vertex
    for u in range(n):
        for v in adj[u]:
            indegree[v] += 1


    # Step 2: queue holds vertices with in-degree 0
    queue = deque(i for i in range(n) if indegree[i] == 0)


    order = []
    while queue:
        u = queue.popleft()      # take a ready vertex
        order.append(u)
        for v in adj[u]:         # free up its neighbours
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)


    if len(order) != n:
        print("Graph has a cycle, no valid order.")
        return


    print("Topological order:", " ".join(map(str, order)))




# A=0, B=1, C=2, D=3, E=4
adj = {
    0: [2],   # A -> C
    1: [2],   # B -> C
    2: [3, 4],# C -> D, C -> E
    3: [],
    4: [],
}
topological_sort(adj, 5)

The output of the above code will be:

Topological order: 0 1 2 3 4

Tip

Every vertex is added to the queue once and removed once. For each vertex we look at all its outgoing edges one time. So the work is O(V + E), where V is the number of vertices and E is the number of edges. The in-degree array uses O(V) extra space.

⏱️ Time and Space Complexity

Here is the cost of Kahn’s algorithm in one place.

Step Time Why
Compute in-degrees O(V + E) We scan every vertex and every edge once.
Process the queue O(V + E) Each vertex enters once, each edge is checked once.
Total time O(V + E) The two passes add up to linear in the graph size.
Extra space O(V) For the in-degree array, the queue, and the order list.

⚠️ Common Mistakes

A few things trip people up the first time:

  • Running it on a graph that has a cycle and expecting an order. There is no valid order then. Always check if the result holds every vertex.
  • Mixing up in-degree and out-degree. We start from vertices with in-degree 0, meaning nothing points into them.
  • Forgetting to push a neighbour the moment its in-degree hits 0. If you skip that, the queue empties early and you lose vertices.
  • Treating the output as the only answer. A DAG can have many valid topological orders. So a different correct order is not a bug.

🧩 What You’ve Learned

  • ✅ Topological sort orders the vertices of a DAG so every edge points from an earlier vertex to a later one.
  • ✅ It models real dependencies like course prerequisites and build tasks, where A must come before B.
  • ✅ Kahn’s algorithm repeatedly removes a vertex with in-degree 0 using a queue, then lowers its neighbours’ in-degrees.
  • ✅ If the final order is missing some vertices, the graph had a cycle and no valid order exists.
  • ✅ The whole thing runs in O(V + E) time with O(V) extra space.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    Topological sort can only be performed on which kind of graph?

    Why: A valid topological order exists only when the directed graph has no cycles, that is, a DAG.

  2. 2

    In Kahn's algorithm, which vertices are pushed into the queue first?

    Why: A vertex with in-degree 0 has no remaining dependencies, so it is safe to process first.

  3. 3

    When you remove a vertex from the queue, what do you do to its neighbours?

    Why: Removing a vertex frees its neighbours, so their in-degree drops by 1, and a neighbour becomes ready when it reaches 0.

  4. 4

    What is the time complexity of Kahn's algorithm?

    Why: Each vertex is processed once and each edge is examined once, giving O(V + E).

Score: 0 / 4

🚀 What’s Next?

Previous Depth-First Search (DFS) Next Dijkstra Shortest Path Algorithm

Share & Connect

Share on LinkedIn