34.02Intermediate / Advanced3 topics17 min3 interactive animations

Topological sort

A topological order lists the vertices of a directed graph so that every arrow goes from an earlier vertex to a later one; it exists exactly when the graph is a DAG, and Kahn's algorithm or DFS finish order builds it in O(n + m).

Learning goals

State when a topological order exists and why there may be several
Run Kahn's algorithm with in-degrees and a queue
Build an order from reversed DFS finish times
Detect a cycle from an incomplete order

Prerequisites

Directed graph fundamentalsBreadth-first searchDepth-first search

To get dressed you put socks on before shoes. To compile a project you build a library before the program that uses it. A topological order is any sequence that respects all such before-and-after rules at once.

34.02.1

Kahn's algorithm

**Kahn's algorithm** repeatedly takes a vertex with in-degree 0, appends it to the order, and deletes its out-arrows, which lowers the in-degree of its heads. A head whose in-degree reaches 0 joins the queue. Counting in-degrees instead of really deleting arrows keeps the work at O(n + m).

The order is not unique: whenever the queue holds several vertices, any choice is valid. Use the *Smallest vertex first* option with a priority queue to get the lexicographically smallest order. Open the first preset and watch the in-degree labels count down.

Java

1static List<Integer> kahnOrder(List<List<Integer>> g) {   // shorter than n when the graph has a cycle
2    int n = g.size();
3    int[] indeg = new int[n];
4    for (List<Integer> out : g) for (int v : out) indeg[v]++;
5    Deque<Integer> queue = new ArrayDeque<>();
6    for (int v = 0; v < n; v++) if (indeg[v] == 0) queue.add(v);   // the sources are ready first
7    List<Integer> order = new ArrayList<>();
8    while (!queue.isEmpty()) {
9        int u = queue.poll();
10        order.add(u);
11        for (int v : g.get(u))
12            if (--indeg[v] == 0) queue.add(v);                     // all of v's prerequisites are placed
13    }
14    return order;
15}

Topological sort: Kahn's algorithm and reversed DFS finish order

Interactive · edit the input

directed graph · 6 vertices · 6 edges

in=2

in=1

in=0

Being processedIn-degree 0 (ready)Placed in the orderFinishedOn a cycle (never ready)

queue (front first)

in-degree

order

none yet

Setup

Count the arrows entering each vertex. The vertices with in-degree 0 have nothing that must precede them: [4, 5].

Step 1 / 14

Java

1List<Integer> kahn(List<List<Integer>> g) {      // topological order; shorter than n on a cycle
2    int n = g.size(); int[] indeg = new int[n];
3    for (List<Integer> out : g) for (int v : out) indeg[v]++;
4    Deque<Integer> q = new ArrayDeque<>();
5    for (int v = 0; v < n; v++) if (indeg[v] == 0) q.add(v);   // sources are ready
6    List<Integer> order = new ArrayList<>();
7    while (!q.isEmpty()) {
8        int u = q.poll(); order.add(u);
9        for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v);   // remove u's arrows
10    }
11    return order;                                // order.size() < n: a cycle remains
12}
13List<Integer> dfsOrder(List<List<Integer>> g) {  // reversed DFS finish order; null on a cycle
14    int n = g.size(); int[] colour = new int[n];
15    Deque<Integer> post = new ArrayDeque<>();
16    for (int s = 0; s < n; s++) if (colour[s] == 0 && !visit(g, s, colour, post)) return null;
17    return new ArrayList<>(post);
18}
19boolean visit(List<List<Integer>> g, int u, int[] colour, Deque<Integer> post) {
20    colour[u] = 1;
21    for (int v : g.get(u)) {
22        if (colour[v] == 1) return false;        // an arrow back into the stack: a cycle
23        if (colour[v] == 0 && !visit(g, v, colour, post)) return false;
24    }
25    colour[u] = 2; post.addFirst(u);             // finished after everything it points to
26    return true;
27}

Live state

0 vertices placed0 arrows removed

sources

[4, 5]

No condition evaluated on this step

Execution trace (dry run table)Show 14 steps

Step	Line	State	What happens
1	L3	sources=[4, 5]	Count the arrows entering each vertex. The vertices with in-degree 0 have nothing that must precede them: [4, 5].
2	L8	u=4 order=[4]	Take 4 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
3	L9	u=4 v=0 indeg[v]=1	4 → 0: in-degree of 0 drops to 1.
4	L9	u=4 v=1 indeg[v]=1	4 → 1: in-degree of 1 drops to 1.
5	L8	u=5 order=[4, 5]	Take 5 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
6	L9	u=5 v=2 indeg[v]=0	5 → 2: in-degree of 2 drops to 0, so 2 is ready and joins the queue.
7	L9	u=5 v=0 indeg[v]=0	5 → 0: in-degree of 0 drops to 0, so 0 is ready and joins the queue.
8	L8	u=2 order=[4, 5, 2]	Take 2 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
9	L9	u=2 v=3 indeg[v]=0	2 → 3: in-degree of 3 drops to 0, so 3 is ready and joins the queue.
10	L8	u=0 order=[4, 5, 2, 0]	Take 0 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
11	L8	u=3 order=[4, 5, 2, 0, 3]	Take 3 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
12	L9	u=3 v=1 indeg[v]=0	3 → 1: in-degree of 1 drops to 0, so 1 is ready and joins the queue.
13	L8	u=1 order=[4, 5, 2, 0, 3, 1]	Take 1 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
14	L11	return=[4, 5, 2, 0, 3, 1]	Topological order: 4 → 5 → 2 → 0 → 3 → 1. All 6 vertices were placed, which also proves the graph is acyclic. Every arrow goes from an earlier vertex to a later one.

34.02.2

DFS finish-order method

Run DFS and record each vertex when it **finishes**. A vertex finishes only after everything it points to has finished (or is already finished), so reading the finish order backwards puts every arrow's tail before its head. Push each finished vertex on the front of a list, or a stack, and the list is the order.

This needs no in-degree array. The arrow into a vertex that is still on the stack is the cycle case: the animation's *DFS finish order* option stops with the cycle it found. The two methods give different valid orders for the same graph, as the first two presets show.

Java

1static List<Integer> dfsTopoOrder(List<List<Integer>> g) {   // empty list when there is a cycle
2    int[] colour = new int[g.size()];
3    Deque<Integer> order = new ArrayDeque<>();
4    for (int s = 0; s < g.size(); s++)
5        if (colour[s] == 0 && !finish(g, s, colour, order)) return new ArrayList<>();
6    return new ArrayList<>(order);
7}
8static boolean finish(List<List<Integer>> g, int u, int[] colour, Deque<Integer> order) {
9    colour[u] = 1;
10    for (int v : g.get(u)) {
11        if (colour[v] == 1) return false;                        // a cycle
12        if (colour[v] == 0 && !finish(g, v, colour, order)) return false;
13    }
14    colour[u] = 2;
15    order.addFirst(u);                                           // everything u points to is already placed after it
16    return true;
17}

Topological sort: Kahn's algorithm and reversed DFS finish order

Interactive · edit the input

directed graph · 6 vertices · 6 edges

in=2

in=1

in=0

Being processedIn-degree 0 (ready)Placed in the orderFinishedOn a cycle (never ready)

queue (front first)

in-degree

order

none yet

Setup

Count the arrows entering each vertex. The vertices with in-degree 0 have nothing that must precede them: [4, 5].

Step 1 / 14

Java

1List<Integer> kahn(List<List<Integer>> g) {      // topological order; shorter than n on a cycle
2    int n = g.size(); int[] indeg = new int[n];
3    for (List<Integer> out : g) for (int v : out) indeg[v]++;
4    Deque<Integer> q = new ArrayDeque<>();
5    for (int v = 0; v < n; v++) if (indeg[v] == 0) q.add(v);   // sources are ready
6    List<Integer> order = new ArrayList<>();
7    while (!q.isEmpty()) {
8        int u = q.poll(); order.add(u);
9        for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v);   // remove u's arrows
10    }
11    return order;                                // order.size() < n: a cycle remains
12}
13List<Integer> dfsOrder(List<List<Integer>> g) {  // reversed DFS finish order; null on a cycle
14    int n = g.size(); int[] colour = new int[n];
15    Deque<Integer> post = new ArrayDeque<>();
16    for (int s = 0; s < n; s++) if (colour[s] == 0 && !visit(g, s, colour, post)) return null;
17    return new ArrayList<>(post);
18}
19boolean visit(List<List<Integer>> g, int u, int[] colour, Deque<Integer> post) {
20    colour[u] = 1;
21    for (int v : g.get(u)) {
22        if (colour[v] == 1) return false;        // an arrow back into the stack: a cycle
23        if (colour[v] == 0 && !visit(g, v, colour, post)) return false;
24    }
25    colour[u] = 2; post.addFirst(u);             // finished after everything it points to
26    return true;
27}

Live state

0 vertices placed0 arrows removed

sources

[4, 5]

No condition evaluated on this step

Execution trace (dry run table)Show 14 steps

Step	Line	State	What happens
1	L3	sources=[4, 5]	Count the arrows entering each vertex. The vertices with in-degree 0 have nothing that must precede them: [4, 5].
2	L8	u=4 order=[4]	Take 4 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
3	L9	u=4 v=0 indeg[v]=1	4 → 0: in-degree of 0 drops to 1.
4	L9	u=4 v=1 indeg[v]=1	4 → 1: in-degree of 1 drops to 1.
5	L8	u=5 order=[4, 5]	Take 5 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
6	L9	u=5 v=2 indeg[v]=0	5 → 2: in-degree of 2 drops to 0, so 2 is ready and joins the queue.
7	L9	u=5 v=0 indeg[v]=0	5 → 0: in-degree of 0 drops to 0, so 0 is ready and joins the queue.
8	L8	u=2 order=[4, 5, 2]	Take 2 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
9	L9	u=2 v=3 indeg[v]=0	2 → 3: in-degree of 3 drops to 0, so 3 is ready and joins the queue.
10	L8	u=0 order=[4, 5, 2, 0]	Take 0 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
11	L8	u=3 order=[4, 5, 2, 0, 3]	Take 3 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
12	L9	u=3 v=1 indeg[v]=0	3 → 1: in-degree of 1 drops to 0, so 1 is ready and joins the queue.
13	L8	u=1 order=[4, 5, 2, 0, 3, 1]	Take 1 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
14	L11	return=[4, 5, 2, 0, 3, 1]	Topological order: 4 → 5 → 2 → 0 → 3 → 1. All 6 vertices were placed, which also proves the graph is acyclic. Every arrow goes from an earlier vertex to a later one.

34.02.3

Cycle detection via incomplete ordering

If the graph has a cycle, no vertex on it ever reaches in-degree 0: each one waits for another vertex of the cycle. Kahn's algorithm therefore stops with fewer than n vertices placed. So *the order has n vertices* is equivalent to *the graph is a DAG*, and this is the simplest directed cycle test.

The unplaced vertices are the cycles and everything that can only be reached through them. They are not necessarily all on a cycle: a vertex that depends on a cyclic part is also stuck. The *Cycle* presets show the stuck vertices highlighted.

Java

1static List<Integer> unplaced(List<List<Integer>> g) {          // empty exactly when g is a DAG
2    int n = g.size();
3    int[] indeg = new int[n];
4    for (List<Integer> out : g) for (int v : out) indeg[v]++;
5    Deque<Integer> queue = new ArrayDeque<>();
6    for (int v = 0; v < n; v++) if (indeg[v] == 0) queue.add(v);
7    boolean[] placed = new boolean[n];
8    while (!queue.isEmpty()) {
9        int u = queue.poll();
10        placed[u] = true;
11        for (int v : g.get(u)) if (--indeg[v] == 0) queue.add(v);
12    }
13    List<Integer> stuck = new ArrayList<>();
14    for (int v = 0; v < n; v++) if (!placed[v]) stuck.add(v);   // on a cycle, or waiting for one
15    return stuck;
16}

Topological sort: Kahn's algorithm and reversed DFS finish order

Interactive · edit the input

directed graph · 6 vertices · 6 edges

in=2

in=1

in=0

Being processedIn-degree 0 (ready)Placed in the orderFinishedOn a cycle (never ready)

queue (front first)

in-degree

order

none yet

Setup

Count the arrows entering each vertex. The vertices with in-degree 0 have nothing that must precede them: [4, 5].

Step 1 / 14

Java

1List<Integer> kahn(List<List<Integer>> g) {      // topological order; shorter than n on a cycle
2    int n = g.size(); int[] indeg = new int[n];
3    for (List<Integer> out : g) for (int v : out) indeg[v]++;
4    Deque<Integer> q = new ArrayDeque<>();
5    for (int v = 0; v < n; v++) if (indeg[v] == 0) q.add(v);   // sources are ready
6    List<Integer> order = new ArrayList<>();
7    while (!q.isEmpty()) {
8        int u = q.poll(); order.add(u);
9        for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v);   // remove u's arrows
10    }
11    return order;                                // order.size() < n: a cycle remains
12}
13List<Integer> dfsOrder(List<List<Integer>> g) {  // reversed DFS finish order; null on a cycle
14    int n = g.size(); int[] colour = new int[n];
15    Deque<Integer> post = new ArrayDeque<>();
16    for (int s = 0; s < n; s++) if (colour[s] == 0 && !visit(g, s, colour, post)) return null;
17    return new ArrayList<>(post);
18}
19boolean visit(List<List<Integer>> g, int u, int[] colour, Deque<Integer> post) {
20    colour[u] = 1;
21    for (int v : g.get(u)) {
22        if (colour[v] == 1) return false;        // an arrow back into the stack: a cycle
23        if (colour[v] == 0 && !visit(g, v, colour, post)) return false;
24    }
25    colour[u] = 2; post.addFirst(u);             // finished after everything it points to
26    return true;
27}

Live state

0 vertices placed0 arrows removed

sources

[4, 5]

No condition evaluated on this step

Execution trace (dry run table)Show 14 steps

Step	Line	State	What happens
1	L3	sources=[4, 5]	Count the arrows entering each vertex. The vertices with in-degree 0 have nothing that must precede them: [4, 5].
2	L8	u=4 order=[4]	Take 4 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
3	L9	u=4 v=0 indeg[v]=1	4 → 0: in-degree of 0 drops to 1.
4	L9	u=4 v=1 indeg[v]=1	4 → 1: in-degree of 1 drops to 1.
5	L8	u=5 order=[4, 5]	Take 5 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
6	L9	u=5 v=2 indeg[v]=0	5 → 2: in-degree of 2 drops to 0, so 2 is ready and joins the queue.
7	L9	u=5 v=0 indeg[v]=0	5 → 0: in-degree of 0 drops to 0, so 0 is ready and joins the queue.
8	L8	u=2 order=[4, 5, 2]	Take 2 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
9	L9	u=2 v=3 indeg[v]=0	2 → 3: in-degree of 3 drops to 0, so 3 is ready and joins the queue.
10	L8	u=0 order=[4, 5, 2, 0]	Take 0 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
11	L8	u=3 order=[4, 5, 2, 0, 3]	Take 3 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
12	L9	u=3 v=1 indeg[v]=0	3 → 1: in-degree of 1 drops to 0, so 1 is ready and joins the queue.
13	L8	u=1 order=[4, 5, 2, 0, 3, 1]	Take 1 and append it to the order. Now remove its out-arrows: each head loses one incoming arrow.
14	L11	return=[4, 5, 2, 0, 3, 1]	Topological order: 4 → 5 → 2 → 0 → 3 → 1. All 6 vertices were placed, which also proves the graph is acyclic. Every arrow goes from an earlier vertex to a later one.

Practice ladder

Now try it yourself

Easy

Find the Town Judge

Medium

Course Schedule
Course Schedule II
Sort Items by Groups Respecting Dependencies

Advanced

Parallel Courses
Sequence Reconstruction

Key takeaways

A topological order exists exactly when the graph is a DAG, and it is usually not unique.
Kahn: repeatedly place an in-degree-0 vertex and lower the in-degrees of its heads; O(n + m).
Reversed DFS finish order is also a valid topological order; an arrow to a grey vertex is a cycle.
Fewer than n vertices placed means a cycle.