Lesson 24.2 · Topological Sort

DFS Finishing Order

A node finishes in DFS only after everything reachable from it has finished. Reverse the finishing order and every edge points forward.

10 min

Think of it like this

Planning a project backwards: before you can call a task done you must finish everything it unlocks. List tasks as they're completely wrapped up, then read the list from the end.

1.Post-order, reversed

Run DFS from every unvisited node. Add a node to a list when its DFS call ends. For any edge u → v, v finishes before u (either it was already finished or it finishes inside u's call), so reversing the list puts u before v.

Combine with the three colours from Module 23 to detect cycles on the way.

Main.java

import java.util.*;

public class Main {
    static List<List<Integer>> adj = new ArrayList<>();
    static boolean[] seen;
    static List<Integer> post = new ArrayList<>();

    static void dfs(int u) {
        seen[u] = true;
        for (int v : adj.get(u)) if (!seen[v]) dfs(v);
        post.add(u);                         // finished: everything after u is done
    }

    public static void main(String[] args) {
        int n = 4;
        int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}};
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) adj.get(e[0]).add(e[1]);
        seen = new boolean[n];
        for (int i = 0; i < n; i++) if (!seen[i]) dfs(i);
        System.out.println("post-order:  " + post);
        List<Integer> topo = new ArrayList<>(post);
        Collections.reverse(topo);
        System.out.println("topological: " + topo);
    }
}

Output

post-order:  [3, 1, 2, 0]
topological: [0, 2, 1, 3]

Remember

Add on finish, then reverse.
Different valid order from Kahn's, equally correct.

Common mistakes

Adding on entry (pre-order isn't a topological order).

Command Palette

DFS Finishing Order

1.Post-order, reversed