☕ DSA Java Articles

Topics › Graphs › Topo Sort and Problems

Topological Sort BFS

Hard TUF ID 2820 SDE

Java source ↗ Edit this article ↗

Problem

You are given a directed acyclic graph (DAG) with V vertices numbered 0 to V - 1, where adj.get(u) lists every v with an edge u -> v. Return a topological order: an arrangement of all V vertices such that for every edge u -> v, u comes before v. Use the breadth-first method, known as Kahn’s algorithm.

A DAG usually has many valid orders, and any of them is accepted. Think of the vertices as tasks and an edge u -> v as “u must be done before v”; a topological order is a schedule that respects every rule.

Constraints: 1 ≤ V ≤ 10^4, 0 ≤ E ≤ 10^5. The Java methods also return an empty array if the input turns out to contain a cycle, since then no order exists.

Example 1

V = 6, edges: 5->2, 5->0, 4->0, 4->1, 2->3, 3->1
answer = [4, 5, 2, 0, 3, 1]    // one valid order; [5, 4, 2, 3, 1, 0] is another

Check a few edges: 5 is before 2, 2 before 3, 3 before 1, 4 before 0.

Example 2

V = 4, edges: 3->0, 1->0, 2->0
answer = [1, 2, 3, 0]          // 0 must be last; the other three are free

Approach 1: Brute force, repeatedly scan for a free vertex

Intuition. Which vertex may go first? Only one that nothing must precede, that is, a vertex with in-degree 0. Place it, and then forget it: delete its outgoing edges, which lowers the in-degree of its successors. The remaining graph is again a DAG, so it again has a vertex with in-degree 0, which can go second. Repeat until all vertices are placed.

A DAG always has such a vertex. Walk backwards from any vertex along incoming arrows; without a cycle you can never return to a vertex, so the walk must end, and it can only end at a vertex with nothing coming in.

The simplest implementation finds the next free vertex by scanning the whole vertex list every time.

Algorithm.

  1. Compute indegree[v] for all vertices.
  2. Repeat V times: scan u = 0..V-1 for the first vertex that is not placed and has indegree[u] == 0.
  3. If none exists, the graph has a cycle; return an empty array.
  4. Place u, then decrement indegree[v] for each edge u -> v.
static int[] bruteForce(int V, List<List<Integer>> adj) {
    int[] indegree = new int[V];
    for (int u = 0; u < V; u++) {
        for (int v : adj.get(u)) indegree[v]++;
    }
    boolean[] placed = new boolean[V];
    int[] order = new int[V];
    for (int k = 0; k < V; k++) {
        int pick = -1;
        for (int u = 0; u < V && pick == -1; u++) {   // full scan for a free vertex
            if (!placed[u] && indegree[u] == 0) pick = u;
        }
        if (pick == -1) return new int[0];            // only possible if the graph has a cycle
        placed[pick] = true;
        order[k] = pick;
        for (int v : adj.get(pick)) indegree[v]--;
    }
    return order;
}

Complexity. Time O(V^2 + E): V scans of V vertices, plus each edge is decremented once. Space O(V).

Because it always picks the smallest free index, this method happens to produce the lexicographically smallest topological order ([4, 5, 0, 2, 3, 1] on example 1). The scan is the only waste: a vertex becomes free at a very specific moment, when its last incoming edge disappears, and we could simply record it then.

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

Intuition. Keep every currently free vertex in a queue. At the start, those are the vertices with in-degree 0. When we remove a vertex u and decrement indegree[v] for each edge u -> v, the in-degree reaching 0 is exactly the moment v becomes free, so we enqueue it right then. No vertex is ever searched for, and each one enters the queue once.

Why is the result a valid order? A vertex is output only after its in-degree has dropped to 0, and in-degrees drop only when predecessors are output. So for every edge u -> v, u is output before v. Why does every vertex get output? Because, as argued above, the remaining graph always has a free vertex while it is acyclic. If the input secretly had a cycle, the vertices on it would never become free and the output would be shorter than V, which is how cycle detection with BFS works.

Algorithm.

  1. Compute in-degrees and enqueue every vertex with in-degree 0.
  2. While the queue is not empty: dequeue u, append it to the order, and for each edge u -> v decrement indegree[v], enqueuing v when it reaches 0.
  3. If V vertices were placed, return the order; otherwise return an empty array.
static int[] optimal(int V, List<List<Integer>> adj) {
    int[] indegree = new int[V];
    for (int u = 0; u < V; u++) {
        for (int v : adj.get(u)) indegree[v]++;
    }
    Deque<Integer> queue = new ArrayDeque<>();
    for (int u = 0; u < V; u++) {
        if (indegree[u] == 0) queue.add(u);
    }
    int[] order = new int[V];
    int k = 0;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        order[k++] = u;
        for (int v : adj.get(u)) {
            if (--indegree[v] == 0) queue.add(v);     // last incoming edge removed: v is free
        }
    }
    return k == V ? order : new int[0];               // fewer than V placed means a cycle
}

Dry run on example 1. The adjacency lists are 5: [2, 0], 4: [0, 1], 2: [3], 3: [1]; initial in-degrees 0:2, 1:2, 2:1, 3:1, 4:0, 5:0.

dequeued in-degree changes newly free queue after order so far
      [4, 5] []
4 0: 2 -> 1, 1: 2 -> 1   [5] [4]
5 2: 1 -> 0, 0: 1 -> 0 2, 0 [2, 0] [4, 5]
2 3: 1 -> 0 3 [0, 3] [4, 5, 2]
0     [3] [4, 5, 2, 0]
3 1: 1 -> 0 1 [1] [4, 5, 2, 0, 3]
1     [] [4, 5, 2, 0, 3, 1]

All six vertices are placed, so the order is returned.

Complexity. Time O(V + E): in-degrees take one pass over the edges, every vertex is enqueued and dequeued once, and every edge is decremented once. Space O(V) for the in-degree array, the queue and the output.

Edge cases and pitfalls