Topological sort¶

Put the tasks of a project in an order where every task comes after the tasks it depends on. Possible exactly when the dependencies have no cycle.

Time	Extra space	Input	Output
\(O(V + E)\)	\(O(V)\)	a directed graph	an order of the vertices, or "there is a cycle"

The idea¶

To get dressed, socks come before shoes and the shirt before the tie. To study algorithms you need programming and data structures first. These "must come before" rules are arrows of a directed graph, and a topological order lists the vertices so that every arrow points forward.

Kahn's algorithm (1962) does what you would do by hand. Count, for each task, how many unfinished tasks it waits for (its in-degree). Any task waiting for nothing can go next. Doing it removes its arrows, which may free other tasks. If at some point tasks remain but none is free, the remaining ones wait on each other in a cycle, and no order exists.

The DFS method is just as short: run depth-first search and list the vertices in reverse order of finishing. A vertex finishes only after everything it points to has finished, so it ends up in front of all of them.

How it works (Kahn)¶

Compute every in-degree; queue every vertex with in-degree 0.
While the queue is not empty: take u, append it to the order, and for each arrow u → v lower indeg[v] by one; if it reaches 0, queue v.
If the order has fewer than \(V\) vertices, the graph has a cycle.

Code¶

The demo orders six courses: 0 maths, 1 programming, 2 data structures, 3 algorithms, 4 databases, 5 machine learning.

PythonJavaC++

from collections import deque


def kahn(n, edges):
    """Topological order of a directed graph (Kahn's algorithm), or None if it has a cycle."""
    adj = [[] for _ in range(n)]
    indeg = [0] * n                          # how many arrows point into each vertex
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    q = deque(v for v in range(n) if indeg[v] == 0)   # nothing has to come before these
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:                     # "remove" u: its arrows no longer count
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else None  # leftovers lie on a cycle


def dfs_topo(n, edges):
    """Topological order by depth-first search: a vertex is finished after everything it points to."""
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
    state = [0] * n                          # 0 = new, 1 = on the current path, 2 = finished
    finished = []

    def visit(u):
        state[u] = 1
        for v in adj[u]:
            if state[v] == 1:
                raise ValueError("cycle")    # an arrow back into the current path
            if state[v] == 0:
                visit(v)
        state[u] = 2
        finished.append(u)
    for u in range(n):
        if state[u] == 0:
            visit(u)
    return finished[::-1]                    # reverse finishing order


if __name__ == "__main__":
    # 0 maths, 1 programming, 2 data structures, 3 algorithms, 4 databases, 5 machine learning
    edges = [(0, 3), (1, 2), (2, 3), (2, 4), (3, 5), (0, 5)]
    print(kahn(6, edges))
    print(dfs_topo(6, edges))
    print(kahn(3, [(0, 1), (1, 2), (2, 0)]))

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class TopologicalSort {
    /** Topological order of a directed graph (Kahn's algorithm), or null if it has a cycle. */
    static List<Integer> kahn(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        int[] indeg = new int[n];                     // how many arrows point into each vertex
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); indeg[e[1]]++; }
        ArrayDeque<Integer> q = new ArrayDeque<>();
        for (int v = 0; v < n; v++) if (indeg[v] == 0) q.add(v);   // nothing has to come before these
        List<Integer> order = new ArrayList<>();
        while (!q.isEmpty()) {
            int u = q.poll();
            order.add(u);
            for (int v : adj.get(u))                  // "remove" u: its arrows no longer count
                if (--indeg[v] == 0) q.add(v);
        }
        return order.size() == n ? order : null;      // leftovers lie on a cycle
    }

    static List<List<Integer>> g;
    static int[] state;                               // 0 = new, 1 = on the current path, 2 = finished
    static List<Integer> finished;

    /** Topological order by depth-first search: a vertex is finished after everything it points to. */
    static List<Integer> dfsTopo(int n, int[][] edges) {
        g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (int[] e : edges) g.get(e[0]).add(e[1]);
        state = new int[n];
        finished = new ArrayList<>();
        for (int u = 0; u < n; u++) if (state[u] == 0) visit(u);
        Collections.reverse(finished);                // reverse finishing order
        return finished;
    }

    static void visit(int u) {
        state[u] = 1;
        for (int v : g.get(u)) {
            if (state[v] == 1) throw new IllegalStateException("cycle");   // an arrow back into the path
            if (state[v] == 0) visit(v);
        }
        state[u] = 2;
        finished.add(u);
    }

    public static void main(String[] args) {
        // 0 maths, 1 programming, 2 data structures, 3 algorithms, 4 databases, 5 machine learning
        int[][] edges = {{0, 3}, {1, 2}, {2, 3}, {2, 4}, {3, 5}, {0, 5}};
        System.out.println(kahn(6, edges));
        System.out.println(dfsTopo(6, edges));
        List<Integer> cyc = kahn(3, new int[][]{{0, 1}, {1, 2}, {2, 0}});
        System.out.println(cyc == null ? "None" : cyc.toString());
    }
}

#include <algorithm>
#include <iostream>
#include <optional>
#include <queue>
#include <stdexcept>
#include <utility>
#include <vector>
using namespace std;

// Topological order of a directed graph (Kahn's algorithm), or nothing if it has a cycle.
optional<vector<int>> kahn(int n, const vector<pair<int, int>>& edges) {
    vector<vector<int>> adj(n);
    vector<int> indeg(n, 0);                         // how many arrows point into each vertex
    for (auto [u, v] : edges) { adj[u].push_back(v); indeg[v]++; }
    queue<int> q;
    for (int v = 0; v < n; v++) if (indeg[v] == 0) q.push(v);   // nothing has to come before these
    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u])                         // "remove" u: its arrows no longer count
            if (--indeg[v] == 0) q.push(v);
    }
    if ((int)order.size() != n) return nullopt;      // leftovers lie on a cycle
    return order;
}

void visit(int u, const vector<vector<int>>& adj, vector<int>& state, vector<int>& finished) {
    state[u] = 1;                                    // 0 = new, 1 = on the current path, 2 = finished
    for (int v : adj[u]) {
        if (state[v] == 1) throw runtime_error("cycle");   // an arrow back into the current path
        if (state[v] == 0) visit(v, adj, state, finished);
    }
    state[u] = 2;
    finished.push_back(u);
}

// Topological order by depth-first search: a vertex is finished after everything it points to.
vector<int> dfsTopo(int n, const vector<pair<int, int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto [u, v] : edges) adj[u].push_back(v);
    vector<int> state(n, 0), finished;
    for (int u = 0; u < n; u++) if (state[u] == 0) visit(u, adj, state, finished);
    reverse(finished.begin(), finished.end());       // reverse finishing order
    return finished;
}

void print(const vector<int>& a) {
    cout << "[";
    for (size_t i = 0; i < a.size(); i++) cout << (i ? ", " : "") << a[i];
    cout << "]\n";
}

int main() {
    // 0 maths, 1 programming, 2 data structures, 3 algorithms, 4 databases, 5 machine learning
    vector<pair<int, int>> edges = {{0, 3}, {1, 2}, {2, 3}, {2, 4}, {3, 5}, {0, 5}};
    print(*kahn(6, edges));
    print(dfsTopo(6, edges));
    auto cyc = kahn(3, {{0, 1}, {1, 2}, {2, 0}});
    if (cyc) print(*cyc); else cout << "None\n";
}

Output: Kahn gives [0, 1, 2, 3, 4, 5], DFS gives [1, 2, 4, 0, 3, 5] (a different order that is just as valid), and the 3-cycle has no order: None.

When to use it¶

Build systems (make, Bazel, compilers ordering modules), package managers installing dependencies first, spreadsheets recalculating cells in order.
Course planning, project scheduling, and the critical path (the longest path in the task graph decides the shortest possible project time).
Shortest and longest paths in a DAG in \(O(V + E)\): relax edges in topological order.
Detecting cycles in dependencies ("circular import").
As a first step for dynamic programming on a DAG: every DP is a walk over its subproblems in topological order.

Common mistakes¶

Not checking for a cycle: Kahn's algorithm silently returns a short list.
Reversing the arrows by mistake ("A depends on B" means the arrow is B → A when "before" is the direction).
In the DFS method, forgetting to reverse the finishing order.
Expecting one answer: most graphs have many valid orders; if you need a specific one (say the smallest number first), use a min-heap instead of the queue in Kahn's algorithm.

Going deeper¶

Each part below starts closed; open the ones you want.

Sample walkthrough: Kahn on the six courses

Arrows: maths → algorithms, maths → ML, programming → data structures, data structures → algorithms, data structures → databases, algorithms → ML.

Take	In-degrees after (0..5)	Newly free	Queue
—	`0, 0, 1, 2, 1, 2`	maths, programming	0, 1
maths (0)	`-, 0, 1, 1, 1, 1`	—	1
programming (1)	`-, -, 0, 1, 1, 1`	data structures	2
data structures (2)	`-, -, -, 0, 0, 1`	algorithms, databases	3, 4
algorithms (3)	`-, -, -, -, 0, 0`	ML	4, 5
databases (4)		—	5
ML (5)		—	empty

The math: existence, correctness and counting

A topological order exists if and only if the graph has no directed cycle. If there is a cycle \(v_1 \to v_2 \to \cdots \to v_k \to v_1\), each \(v_i\) must come before \(v_{i+1}\) and \(v_k\) before \(v_1\): impossible. Conversely, a DAG always has a vertex with in-degree 0 (follow arrows backwards; with no cycle you must stop), so you can put it first, delete it, and repeat on the smaller DAG.

Kahn is correct. A vertex is output only when all its predecessors have been output, so all arrows point forward. If a cycle exists, no vertex on it can ever reach in-degree 0, so fewer than \(V\) vertices are output.

DFS is correct. For any arrow \(u \to v\) in a DAG, \(f[v] < f[u]\): when DFS meets the arrow, \(v\) is either unseen (it is then finished inside \(u\)'s call) or already finished; it cannot be on the current path, as that would be a cycle. So sorting by decreasing finish time puts \(u\) before \(v\).

Time. Each vertex is queued once and each arrow decreases one in-degree once: \(O(V + E)\).

How many orders? Counting topological orders is #P-complete in general (Brightwell and Winkler, 1991); listing them all is a backtracking job.

Watch it step by step

Numbers are the arrows still coming in. Blue vertices are free to go next; purple is the one just taken; removed arrows fade.

Variations and related ideas

Lexicographically smallest order: a min-heap in place of the queue, \(O(V \log V + E)\).
Parallel scheduling: process Kahn's queue in rounds; the number of rounds is the length of the longest path, the least time with unlimited workers.
Critical path method (CPM) and PERT in project management.
Tarjan's SCC algorithm outputs the components of any directed graph in reverse topological order.

References¶

A. B. Kahn, "Topological sorting of large networks", Communications of the ACM 5(11), 1962.
T. H. Cormen et al., Introduction to Algorithms, 4th ed., §20.4 (topological sort).
D. E. Knuth, The Art of Computer Programming, Vol. 1, 3rd ed., §2.2.3.