Topological sort

Introduction

Some tasks must wait for others: you take Data Structures before Algorithms, and you put on socks before shoes. Draw each task as a vertex and each "must come before" as a directed edge. A topological order lists the vertices so that every edge goes from earlier to later.

That is only possible when the graph has no cycle (if A needs B and B needs A, neither can go first). A directed graph without cycles is a DAG (directed acyclic graph).

Any time a program must work out what to do first, this is the algorithm behind it. Getting dressed, compiling a large program and planning a degree all have the same shape.

How it works

There are two classic methods. Kahn's algorithm, worked through in the Example section below, keeps taking a task that has nothing left to wait for. The other method gets an order from depth-first search.

With depth-first search

DFS gives another method: run DFS, and add each vertex to the front of the answer when its call finishes (after all its descendants). A vertex finishes only after everything that depends on it, so the finished order, reversed, is topological.

Syntax

if (indegree[v] == 0) queue[rear++] = v;       // ready to go

int u = queue[front++];                        // take one
for each edge u -> v:
    if (--indegree[v] == 0) queue[rear++] = v; // v is now ready

Example

#include <stdio.h>
#define N 5

int main(void) {
    const char *name[N] = {"Programming", "Discrete Math", "Data Structures", "Algorithms", "Operating Systems"};
    int edge[N][N] = {0};   // edge[u][v] = 1: take u before v
    edge[0][2] = 1;
    edge[2][3] = 1;
    edge[1][3] = 1;
    edge[2][4] = 1;
    int indegree[N] = {0};
    for (int u = 0; u < N; u++)
        for (int v = 0; v < N; v++)
            if (edge[u][v]) indegree[v]++;
    int queue[N], front = 0, rear = 0;
    for (int v = 0; v < N; v++)
        if (indegree[v] == 0) queue[rear++] = v;
    int done = 0;
    while (front < rear) {
        int u = queue[front++];
        printf("%d. %s\n", ++done, name[u]);
        for (int v = 0; v < N; v++) {
            if (edge[u][v] && --indegree[v] == 0) queue[rear++] = v;
        }
    }
    if (done < N) printf("there is a cycle\n");
    return 0;
}

The in-degree of a vertex is the number of edges coming into it: how many tasks it still waits for.

1. Put every vertex with in-degree 0 (nothing to wait for) in a queue.
2. Take a vertex from the queue and output it. Remove its outgoing edges: lower each neighbour's in-degree by 1, and enqueue any neighbour that reaches 0.
3. Repeat until the queue is empty.

If fewer than n vertices were output, the rest are stuck waiting on each other: the graph has a cycle. With adjacency lists it is O(n + m); this example uses a matrix, so O(n²).

A graph can have several topological orders; any one that respects every edge is correct.

Line by line

1. name holds the five course names, and edge[u][v] is 1 when u must come before v.
2. The two loops add 1 to indegree[v] for each edge coming into v.
3. Every vertex with in-degree 0 goes into the queue, since it waits for nothing.
4. The while loop takes a vertex from the queue and prints it, with done as its number.
5. For each edge out of u, the in-degree of v drops by 1. At 0, v joins the queue.
6. After the loop, done < N would mean some vertices never became ready, which only a cycle can cause.

Expected result

1. Programming
2. Discrete Math
3. Data Structures
4. Algorithms
5. Operating Systems

In the real world

Build tools such as make, package managers that install dependencies in the right order, and spreadsheets that recalculate cells all use a topological order. They also use cycle detection to report an error such as a circular reference.

Common mistakes

• Pointing edges the wrong way, so that tasks come out in reverse order.
• Forgetting the check at the end, and printing a partial order as if it were complete.
• Assuming the order is unique: most graphs have several correct orders.

Best practices

• Decide what an edge means and write it down.
• Always report a cycle, instead of ignoring the vertices left over.
• Use adjacency lists when the graph is large and has few edges.

Summary

A topological order lists the vertices of a DAG so that every edge goes forward. Kahn's algorithm finds one by repeatedly removing vertices with in-degree 0, and leftover vertices reveal a cycle.

Mark lesson complete