☕ DSA Java Articles

Topics › Graphs › Topo Sort and Problems

Topo Sort

Hard TUF ID 2822 A2Z

Java source ↗ Edit this article ↗

Problem

You are given a directed acyclic graph (DAG) with V vertices numbered 0 to V - 1, as an adjacency list. Return a topological order: a list containing every vertex exactly once, such that for every edge u -> v, u appears before v. When several orders are valid, any of them is accepted.

Think of vertices as tasks and an edge u -> v as “u must be done before v”. A topological order is a schedule that respects every such rule. Constraints: 1 ≤ V ≤ 10^4, 0 ≤ E ≤ V·(V-1)/2.

Example 1

5 -> 0 <- 4
|         |
v         v
2 -> 3 -> 1
edges: 5->0, 5->2, 4->0, 4->1, 2->3, 3->1
one answer: [5, 4, 2, 3, 1, 0]       // [4, 5, 0, 2, 3, 1] is also valid

Example 2

edges: 0->1, 1->2, 2->3
answer: [0, 1, 2, 3]                 // a chain has exactly one valid order

Why must the graph be acyclic? If a -> b -> ... -> a were a cycle, a would have to come before itself. So topological orders exist exactly for DAGs. This article assumes the input is a DAG, as the A2Z problem does.

Approach 1: Brute force, repeatedly take a vertex with no incoming edge

Intuition. Some vertex in a DAG has no incoming edges. If every vertex had one, we could keep walking edges backwards forever, and with finitely many vertices we would revisit one, which would be a cycle. A vertex with no incoming edges depends on nothing, so it can safely go first. Remove it; the rest is still a DAG, so it again has such a vertex. Repeat until all vertices are placed.

The naive version recomputes, every round, which unplaced vertices still have an incoming edge from another unplaced vertex.

Algorithm.

  1. Repeat V times:
  2. Mark every vertex that has an incoming edge from a vertex not yet placed.
  3. Pick the smallest unplaced vertex without such a mark, and append it to the order.
static int[] bruteForce(int V, List<List<Integer>> adj) {
    boolean[] placed = new boolean[V];
    int[] order = new int[V];
    for (int k = 0; k < V; k++) {
        boolean[] hasIncoming = new boolean[V];     // incoming edge from a vertex that is not placed yet
        for (int u = 0; u < V; u++) {
            if (!placed[u]) for (int v : adj.get(u)) hasIncoming[v] = true;
        }
        int pick = -1;
        for (int v = 0; v < V && pick == -1; v++) {
            if (!placed[v] && !hasIncoming[v]) pick = v;
        }
        if (pick == -1) return new int[0];           // impossible in a DAG: every remaining vertex is on or after a cycle
        placed[pick] = true;
        order[k] = pick;
    }
    return order;
}

Complexity. Time O(V · (V + E)): V rounds, each scanning all edges. Space O(V). Keeping in-degree counters and a queue instead of rescanning turns this into Kahn’s algorithm, which runs in O(V + E) and is covered in Topological sort or Kahn’s algorithm.

Approach 2: Optimal, DFS finishing order

Intuition. Run DFS and push each vertex onto a stack at the moment its call finishes, after all its outgoing edges have been fully explored. Then pop the stack.

When dfs(u) finishes, every vertex reachable from u has already finished and was pushed earlier. Since u is pushed after all of them, it sits above them in the stack and is popped before them. That is exactly the requirement: u before everything that depends on it.

More carefully, take any edge u -> v and look at the moment dfs(u) examines it:

In every possible case v is pushed before u, so u comes out of the stack before v.

Algorithm.

  1. For each unvisited vertex s, in order, call dfs(s).
  2. dfs(u): mark u, recurse into each unvisited neighbour, then push u.
  3. Pop the stack into the answer array.
static int[] optimal(int V, List<List<Integer>> adj) {
    boolean[] vis = new boolean[V];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int s = 0; s < V; s++) {
        if (!vis[s]) dfs(s, adj, vis, stack);
    }
    int[] order = new int[V];
    for (int k = 0; k < V; k++) order[k] = stack.pop();
    return order;
}

static void dfs(int u, List<List<Integer>> adj, boolean[] vis, Deque<Integer> stack) {
    vis[u] = true;
    for (int v : adj.get(u)) {
        if (!vis[v]) dfs(v, adj, vis, stack);
    }
    stack.push(u);                                   // everything reachable from u is already on the stack
}

Dry run on Example 1 (stack written top first):

outer vertex what happens stack after
0 no outgoing edges, push 0 0
1 no outgoing edges, push 1 1 0
2 dfs(2) -> dfs(3); 1 is visited; push 3, then push 2 2 3 1 0
3 already visited 2 3 1 0
4 0 and 1 visited, push 4 4 2 3 1 0
5 0 and 2 visited, push 5 5 4 2 3 1 0

Popping gives [5, 4, 2, 3, 1, 0]. Check one edge: 2 -> 3 holds because 3 was pushed before 2.

Complexity. Time O(V + E): each vertex is visited once and each edge examined once. Space O(V) for vis, the stack and the recursion.

Edge cases and pitfalls