☕ DSA Java Articles

Topics › Graphs › Topo Sort and Problems

Topological sort or Kahn's algorithm

Hard TUF ID 502 A2Z

Java source ↗ Edit this article ↗

Problem

You are given a directed graph with V vertices numbered 0 to V - 1, as an adjacency list. Return a topological order computed with BFS, the method known as Kahn’s algorithm: every vertex appears exactly once, and for every edge u -> v, u comes before v. Any valid order is accepted.

The A2Z problem promises a DAG. This version also handles cyclic input, where no topological order exists, by returning an empty array. Kahn’s algorithm notices this for free, which is one of its main attractions.

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
Kahn's answer: [4, 5, 0, 2, 3, 1]

Example 2

edges: 0->1, 1->2, 2->0
answer: []          // 0, 1, 2 each wait for another: no vertex can go first

The central quantity is the in-degree of a vertex: the number of edges pointing into it, which is the number of things that must happen before it. A vertex with in-degree 0 can be scheduled right now. Placing a vertex u satisfies one prerequisite of each v with u -> v, so their in-degrees drop by one.

Approach 1: Brute force, scan for a free vertex each round

Intuition. Compute all in-degrees once. Then repeat: find an unplaced vertex whose in-degree is 0, place it, and decrement the in-degrees of its out-neighbours. Every placed vertex only ever had already-placed predecessors, so the order is valid.

If at some round no unplaced vertex has in-degree 0, every remaining vertex has an incoming edge from another remaining vertex. Following those edges backwards forever must revisit a vertex, so the remaining vertices contain a cycle and we return an empty array.

Algorithm.

  1. Compute indeg for every vertex.
  2. Repeat V times: scan for the smallest unplaced v with indeg[v] == 0. If none exists, return [].
  3. Place v and decrement indeg of each out-neighbour.
static int[] bruteForce(int V, List<List<Integer>> adj) {
    int[] indeg = new int[V];
    for (int u = 0; u < V; u++) for (int v : adj.get(u)) indeg[v]++;
    boolean[] placed = new boolean[V];
    int[] order = new int[V];
    for (int k = 0; k < V; k++) {
        int pick = -1;
        for (int v = 0; v < V && pick == -1; v++) {
            if (!placed[v] && indeg[v] == 0) pick = v;
        }
        if (pick == -1) return new int[0];           // every remaining vertex still has an incoming edge: cycle
        placed[pick] = true;
        order[k] = pick;
        for (int v : adj.get(pick)) indeg[v]--;
    }
    return order;
}

Complexity. Time O(V^2 + E): V linear scans, plus each edge decremented once. Space O(V). The scans are the waste: almost every round re-inspects vertices that cannot possibly have changed.

Approach 2: Optimal, Kahn’s algorithm with a queue

Intuition. A vertex’s in-degree only changes when one of its predecessors is placed, and it becomes ready at the exact moment that its in-degree drops to 0. So rather than searching for ready vertices, push each one into a queue at that moment. The queue always holds precisely the vertices that are ready but not yet placed.

Each vertex enters the queue once, at the moment its last prerequisite is placed, and each edge causes one decrement. At the end, count the placed vertices. If fewer than V were placed, some vertices never reached in-degree 0. A vertex on a cycle always keeps an incoming edge from the previous cycle vertex, which itself is never placed, so none of the cycle is placed, and neither is anything that depends on the cycle. So placed < V is exactly the signal that a cycle exists.

Algorithm.

  1. Compute indeg; enqueue every vertex with in-degree 0.
  2. While the queue is not empty: pop u, append it to the order, and for each u -> v decrement indeg[v], enqueuing v when it reaches 0.
  3. Return the order if it has V vertices, otherwise [].
static int[] kahn(int V, List<List<Integer>> adj) {
    int[] indeg = new int[V];
    for (int u = 0; u < V; u++) for (int v : adj.get(u)) indeg[v]++;
    Deque<Integer> q = new ArrayDeque<>();
    for (int v = 0; v < V; v++) if (indeg[v] == 0) q.offer(v);
    int[] order = new int[V];
    int k = 0;
    while (!q.isEmpty()) {
        int u = q.poll();
        order[k++] = u;
        for (int v : adj.get(u)) {
            if (--indeg[v] == 0) q.offer(v);         // u was v's last unplaced prerequisite
        }
    }
    return k == V ? order : new int[0];              // vertices never freed sit on or behind a cycle
}

Dry run on Example 1. Initial in-degrees: 0:2, 1:2, 2:1, 3:1, 4:0, 5:0.

pop order so far in-degree changes queue after
      4, 5
4 4 0: 2→1, 1: 2→1 5
5 4 5 0: 1→0, 2: 1→0 0, 2
0 4 5 0 none 2
2 4 5 0 2 3: 1→0 3
3 4 5 0 2 3 1: 1→0 1
1 4 5 0 2 3 1 none empty

Six vertices placed, so [4, 5, 0, 2, 3, 1] is returned. On Example 2 every in-degree starts at 1, the queue starts empty, nothing is placed, and the result is [].

Complexity. Time O(V + E): building in-degrees touches each edge once, and so does the main loop. Space O(V) for indeg, the queue and the order.

Approach 3: Lexicographically smallest order with a min-heap

Intuition. A common follow-up asks for the smallest topological order in dictionary order, for example “print the tasks, and among equally ready tasks always pick the lowest number”. The only change is to replace the FIFO queue by a min-heap, so the smallest ready vertex is always placed next.

Taking the smallest ready vertex at every step is the right greedy here. Whatever vertex is placed first must be a ready one, so the smallest ready vertex is the best possible first entry; the same argument applies to each later position. The brute force above also picks the smallest free vertex each round, so it produces exactly this order, and the tests check that the two agree.

static int[] kahnSmallestFirst(int V, List<List<Integer>> adj) {
    int[] indeg = new int[V];
    for (int u = 0; u < V; u++) for (int v : adj.get(u)) indeg[v]++;
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int v = 0; v < V; v++) if (indeg[v] == 0) pq.offer(v);
    int[] order = new int[V];
    int k = 0;
    while (!pq.isEmpty()) {
        int u = pq.poll();
        order[k++] = u;
        for (int v : adj.get(u)) {
            if (--indeg[v] == 0) pq.offer(v);
        }
    }
    return k == V ? order : new int[0];
}

Complexity. Time O((V + E) log V) for the heap operations. Space O(V).

For the edges 0 -> 3 and 1 -> 2, plain Kahn’s gives [0, 1, 3, 2] because 3 joins the queue before 2, while the min-heap version gives [0, 1, 2, 3]. Both are valid.

Edge cases and pitfalls