Topological Sort

The idea

You can’t take Algorithms before Data Structures, and you can’t take Data Structures before Programming. Draw an arrow A → B for every “A must come before B” rule and you get a directed graph. A topological sort lists all the nodes so that every arrow points forward: each node comes after everything it depends on.

Two facts to remember:

• A topological order exists only if the graph has no cycle. If A must come before B and B before A, no order can work. A directed graph without cycles is called a DAG (directed acyclic graph).
• The order is usually not unique. Prog, Maths, … and Maths, Prog, … can both be correct.

Kahn’s algorithm (using in-degrees)

The in-degree of a node is the number of arrows coming into it: how many things it is still waiting for.

1. Compute every in-degree.
2. Put every node with in-degree 0 into a queue. These have nothing to wait for.
3. Repeatedly take a node from the queue, add it to the order, and remove its outgoing arrows. Each target’s in-degree drops by 1. When one reaches 0, it joins the queue.
4. If fewer than V nodes came out, the leftover nodes are stuck in a cycle.

On the course plan from the 3D model:

The DFS method

Run a depth-first search. A node finishes when everything reachable from it has finished, so a node must come before everything that finished earlier. Each node is therefore placed at the front of the order when it finishes. Equivalently, take the finishing order and reverse it.

If DFS ever follows an arrow to a node that is still in progress (still on the recursion stack), it has walked around a loop, so the graph has a cycle.

Code

from collections import deque

def kahn(nodes, edges):
    indeg = {v: 0 for v in nodes}
    adj = {v: [] for v in nodes}
    for a, b in edges:
        adj[a].append(b)
        indeg[b] += 1
    queue = deque(v for v in nodes if indeg[v] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    if len(order) < len(nodes):
        raise ValueError("cycle: no topological order")
    return order

def dfs_topo(nodes, edges):
    adj = {v: [] for v in nodes}
    for a, b in edges:
        adj[a].append(b)
    state, order = {}, []            # 1 = in progress, 2 = finished
    def visit(u):
        state[u] = 1
        for v in adj[u]:
            if state.get(v) == 1:
                raise ValueError("cycle: no topological order")
            if v not in state:
                visit(v)
        state[u] = 2
        order.append(u)              # u has finished
    for v in nodes:
        if v not in state:
            visit(v)
    return order[::-1]               # reverse of the finishing order

nodes = ["Prog", "Maths", "DS", "COA", "Algo", "OS", "DBMS", "ML"]
edges = [("Prog", "DS"), ("Maths", "DS"), ("Prog", "COA"), ("DS", "Algo"),
         ("DS", "OS"), ("COA", "OS"), ("DS", "DBMS"), ("Algo", "ML"), ("Maths", "ML")]
print(kahn(nodes, edges))
# ['Prog', 'Maths', 'COA', 'DS', 'Algo', 'OS', 'DBMS', 'ML']
print(dfs_topo(nodes, edges))
# ['Maths', 'Prog', 'COA', 'DS', 'DBMS', 'OS', 'Algo', 'ML']

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// Kahn's algorithm. Returns an empty vector if the graph has a cycle.
vector<int> topoSort(int n, const vector<pair<int, int>>& edges) {
    vector<vector<int>> adj(n);
    vector<int> indeg(n, 0), order;
    for (auto [a, b] : edges) { adj[a].push_back(b); indeg[b]++; }
    queue<int> q;
    for (int v = 0; v < n; v++) if (indeg[v] == 0) q.push(v);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
    }
    if ((int)order.size() < n) return {};   // cycle
    return order;
}

int main() {
    // 0 Prog, 1 Maths, 2 DS, 3 COA, 4 Algo, 5 OS, 6 DBMS, 7 ML
    vector<pair<int, int>> edges = {{0,2},{1,2},{0,3},{2,4},{2,5},{3,5},{2,6},{4,7},{1,7}};
    for (int v : topoSort(8, edges)) cout << v << " ";   // 0 1 3 2 4 5 6 7
}

Analysis

Both methods touch every node once and every edge once, so both run in O(V + E) time with an adjacency list. Kahn’s algorithm needs the in-degree array and a queue. The DFS method needs the visited state and the recursion stack. Both use O(V) extra space.

Need the alphabetically smallest valid order? Use Kahn’s algorithm with a min-heap instead of a plain queue.

Where is it used?

• Build tools (make, Gradle, Bazel) compile files after the files they depend on.
• Package managers (npm, pip, apt) install dependencies before the packages that need them.
• Spreadsheets recalculate a cell after the cells its formula uses.
• Course planning and project scheduling: which task can start next?
• Shortest and longest paths in a DAG can be found in O(V + E) by relaxing edges in topological order.

Common mistakes

• Trying to topologically sort an undirected graph. It only makes sense for directed edges.
• Forgetting isolated nodes (no edges at all). They have in-degree 0 and belong in the order too.
• In the DFS method, adding a node to the end when it finishes and forgetting to reverse the list.
• Assuming the answer is unique. Many valid orders usually exist.