Topological sort

Prerequisites

• Directed graphs (see representations).
• Queue.
• DFS, for the alternative method.

The analogy

How it works

Precondition: a directed acyclic graph (DAG). If there is a cycle, no valid order exists, and the algorithm reports it.

Start with the course plan by hand

Edges (prerequisite → course): 0 → 1, 0 → 2, 1 → 3, 2 → 3. In-degree = number of unfinished prerequisites. Kahn's method: queue every vertex with in-degree 0, then repeatedly take one, output it, and lower its successors' in-degrees. Predict, then open "Check".

Finish the picture: more orders, and a cycle

Topological orders are not always unique, and sometimes none exists.

• Another order. Predict a second valid order for the course plan.
  Check

  0, 2, 1, 3: Maths before Data structures works too, since neither depends on the other.

• Add the edge 3 → 0. Predict what Kahn's method does.
  Check

  Every vertex now has in-degree ≥ 1, so the queue starts empty and nothing is output: 0 < 4 vertices, so there is a cycle.

The rule in plain words

Compute every vertex's in-degree. Put all in-degree-0 vertices in a queue.

Repeat: dequeue a vertex, append it to the order, and decrement its successors' in-degrees, enqueueing any that reach 0. If the order has fewer than $V$ vertices, the graph has a cycle.

The code

Read this code after you have sorted the course plan by hand. It will make more sense.

int topo_sort(int adj[][4], int n, int order[]) {   /* returns how many were ordered */
    int indeg[100];
    int queue[100];
    int head = 0, tail = 0;
    for (int v = 0; v < n; v++) { indeg[v] = 0; for (int u = 0; u < n; u++) indeg[v] += adj[u][v]; }
    for (int v = 0; v < n; v++) if (indeg[v] == 0) queue[tail++] = v;   /* no prerequisites */
    while (head < tail) {
        int u = queue[head++];
        order[head - 1] = u;
        for (int v = 0; v < n; v++)
            if (adj[u][v] && --indeg[v] == 0) queue[tail++] = v;     /* last prerequisite done */
    }
    return head;                                    /* < n means there is a cycle */
}

graph LR
  I["Intro (0)"] --> D["Data structures (1)"]
  I --> M["Maths (2)"]
  D --> A["Algorithms (3)"]
  M --> A
          

How fast is it?

Each vertex enters and leaves the queue once, and each edge decrements one in-degree once:

The DFS method has the same cost: run DFS and output vertices in reverse finish order.

Common mistakes

• Forgetting to check for cycles, so a partial order is returned silently.
• Using DFS visit (pre-order) order instead of reverse finish order.
• Claiming the topological order is unique.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• In-degree-0 vertices go first because nothing has to come before them.
• Outputting a vertex can unlock others because it removes one prerequisite from each successor.
• It costs $O(V + E)$ because each vertex and edge is handled once.
• Fewer than $V$ outputs means a cycle because vertices on a cycle always keep an unfinished prerequisite.
• Several orders can be valid because independent tasks can go in any relative order.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is topological sort like getting dressed?
   Sample answer

   Some items must come before others (socks before shoes), but independent items can go in any order; you find an order that respects every "before".

2. Walk through Kahn's method on 0 → 1, 0 → 2, 1 → 3, 2 → 3.
   Sample answer

   In-degrees 0, 1, 1, 2; queue [0]. Output 0, queue 1 and 2; output 1 (3 drops to 1); output 2 (3 drops to 0, enqueue); output 3. Order 0, 1, 2, 3.

3. Why does the code use --indeg[v] == 0 inside the loop?

   A good answer says when a vertex becomes free.

   Sample answer

   Outputting u removes one prerequisite of v. When the count reaches exactly 0, v's last prerequisite is done, so it is enqueued then, and only once.

4. So what is a topological sort, in one sentence?
   Sample answer

   An ordering of the vertices of a DAG such that every edge points from an earlier vertex to a later one.

5. Why does a cycle make topological sorting impossible?

   A good answer looks at the first vertex of the cycle in any order.

   Sample answer

   In any order, some vertex of the cycle comes first, but the cycle has an edge into it from a later vertex, breaking the rule. Kahn's method shows this as vertices that never reach in-degree 0.

6. What does topological sort cost?
   Sample answer

   $O(V + E)$ with adjacency lists, $O(V)$ extra space.

7. How would you do it with DFS instead?
   Sample answer

   Run DFS from every unvisited vertex and record vertices when they finish; the reverse of that finish order is a topological order.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the DFS method and the matrix code. I'd keep the getting-dressed analogy, the course plan with in-degrees, and "start with no prerequisites, unlock as you go, no cycles allowed".

External resources

• VisuAlgo: Graph traversal: includes topological sort with both methods.
• GeeksforGeeks: Kahn's algorithm: code and cycle detection.
• Wikipedia: Topological sorting: both algorithms and applications.

Videos

• YouTube search: Kahn's topological sort: pick a walkthrough with in-degrees.