4.19.2 — Ordering & Connectivity: Topological Sort, Cycles, Union-Find & MST

Two questions come up whenever a graph models dependencies:

• "In what order can I do these tasks, so that nothing runs before what it depends on?" — a build system compiling modules, a package manager installing dependencies, a university checking course prerequisites, a database applying migrations.
• "Is there a cycle?" — because if A depends on B and B depends on A, there is no valid order at all, and the honest answer is to report the cycle rather than pick arbitrarily.

Those two questions are the same question. An ordering exists if and only if the graph is a DAG, so the algorithm that produces the order also detects the failure.

1. Topological sort by counting incoming edges (Kahn's algorithm)

The intuition is exactly how you would do it by hand. Find something with no unmet prerequisites, do it, cross it off, and see what that unblocks.

function topoSort(numTasks: number, edges: [number, number][]): number[] | null {
  const adj: number[][] = Array.from({ length: numTasks }, () => []);
  const inDegree = new Array(numTasks).fill(0);              // (1)

  for (const [before, after] of edges) {                     // (2)
    adj[before].push(after);
    inDegree[after]++;
  }

  const queue: number[] = [];
  for (let i = 0; i < numTasks; i++) if (inDegree[i] === 0) queue.push(i);   // (3)

  const order: number[] = [];
  let head = 0;
  while (head < queue.length) {
    const task = queue[head++];
    order.push(task);                                        // (4)
    for (const next of adj[task]) {
      if (--inDegree[next] === 0) queue.push(next);          // (5)
    }
  }

  return order.length === numTasks ? order : null;           // (6)
}

1. inDegree[i] counts how many prerequisites task i still has outstanding.
2. Edge before → after means "before must happen first", so it adds one to after's count.
3. Anything with zero prerequisites can start immediately. There may be several, and any of them is a valid first choice — which is why a topological order is not unique.
4. Emit it.
5. The heart of the algorithm. Finishing a task removes one prerequisite from each of its dependents. When a dependent's count reaches zero, it is now runnable. The pre-decrement means we test the value after the decrement.
6. The cycle check, and it is free. If some tasks are in a cycle, every member of that cycle always has at least one unmet prerequisite (another member), so none of them ever reaches zero and none is ever emitted. So a short output means a cycle exists. No separate cycle-detection pass is needed.

O(V + E) time and O(V) space. Every vertex is enqueued once and each edge is decremented once.

Why this matters beyond interviews. A build tool runs exactly this over your module graph. npm install runs it over the dependency tree. A migration runner runs it over migration files. And when it returns null, the tool prints "circular dependency detected", which you have almost certainly seen.

The parallel-scheduling bonus. Everything in the queue at the same moment has no dependency on anything else in the queue, so those tasks can run simultaneously. Process the queue level by level and the number of levels is the minimum time to finish with unlimited workers. That is why build systems compile in waves.

2. Topological sort by DFS, and why post-order gives the reverse

The other route uses the DFS post-order position from Chapter 4.19.1.

function topoSortDfs(numTasks: number, adj: number[][]): number[] | null {
  const state = new Array(numTasks).fill(0);   // (1)  0 = unvisited, 1 = in progress, 2 = done
  const order: number[] = [];

  const visit = (node: number): boolean => {
    if (state[node] === 1) return false;       // (2)  ← back edge = cycle
    if (state[node] === 2) return true;        // (3)  already finished
    state[node] = 1;                           // (4)  entering
    for (const next of adj[node]) if (!visit(next)) return false;
    state[node] = 2;                           // (5)  leaving
    order.push(node);                          // (6)  post-order
    return true;
  };

  for (let i = 0; i < numTasks; i++) if (state[i] === 0 && !visit(i)) return null;
  return order.reverse();                      // (7)
}

1. Three states, not two. This is the whole trick, and using a plain visited boolean is the classic wrong answer.
2. State 1 means "this node is an ancestor of the node we are currently at, still on the recursion stack". Reaching it again means we have followed a path that loops back on itself — a back edge, which is exactly a cycle.
3. State 2 means the node was finished in an earlier branch. Reaching it again is perfectly fine: two different tasks can share a prerequisite. A two-state visited set cannot tell case 2 from case 3, so it reports false cycles.
4. Mark on the way in.
5. Mark done on the way out, after every descendant has finished.
6. Push in post-order. At this moment every task that depends on nothing but this node's descendants is already in the list, so this node must come before all of them in the final order. Appending it here and reversing at the end achieves that.
7. Reverse, because post-order emits dependencies first and we appended them first.

The two algorithms compared. Kahn's is iterative, so no stack-overflow risk, and it gives the parallel-wave structure for free. DFS is shorter and naturally reports where the cycle is, since the recursion stack holds the cycle when you hit a grey node. Both are O(V+E); pick whichever the problem's follow-up favours.

Cycle detection in an undirected graph is a different problem. There is no direction, so every edge looks like a back edge to the node you just came from. The fix is to pass the parent down and skip it:

const hasCycle = (node: number, parent: number): boolean => {
  visited.add(node);
  for (const next of adj[node]) {
    if (next === parent) continue;                  // ← the edge we arrived on
    if (visited.has(next)) return true;
    if (hasCycle(next, node)) return true;
  }
  return false;
};

Skipping only the immediate parent is correct because any other already-visited neighbour must have been reached by a different route, which closes a genuine cycle.

3. Union-find: connectivity without traversal

BFS and DFS answer "are A and B connected" in O(V+E) per query. If you have to answer it a million times while edges are being added, that is far too slow.

Union-find (also called disjoint set union) answers it in effectively constant time, using an idea that looks too simple to work: each group is a tree, and a group is identified by the root of its tree. Two elements are connected exactly when they have the same root.

class UnionFind {
  private parent: number[];
  private size: number[];                                    // (1)
  count: number;                                             // (2)

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);    // (3)  everyone is their own root
    this.size = new Array(n).fill(1);
    this.count = n;
  }

  find(x: number): number {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]];          // (4)  path halving
      x = this.parent[x];
    }
    return x;
  }

  union(a: number, b: number): boolean {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;                             // (5)  already together
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];  // (6)  union by size
    this.parent[rb] = ra;
    this.size[ra] += this.size[rb];
    this.count--;                                            // (7)
    return true;
  }

  connected(a: number, b: number): boolean { return this.find(a) === this.find(b); }
}

1. The number of elements in each root's group, used to keep the trees shallow.

2. How many separate groups exist right now. Free to maintain, and it answers "how many connected components" with no extra work.

3. Every element starts alone, as its own root.

4. Path halving. While walking up to the root, point each node at its grandparent. This flattens the tree as a side effect of asking a question, so later queries are shorter. The alternative is full path compression — a second pass repointing everything directly at the root — which is slightly better asymptotically and needs recursion or a second loop. Path halving gets the same practical result in one pass.

5. Returning false when they were already connected is useful: it means "this edge would create a cycle", which is exactly what Kruskal's algorithm in section 4 needs.

6. Union by size. Always hang the smaller tree under the larger root. Without this, unioning in a bad order builds a chain of length n and find becomes O(n). The variant union by rank uses tree height instead of size; both work.

7. Every successful union merges two groups into one.

The complexity is the famous part. With both path compression and union by size, m operations on n elements cost O(m \cdot \alpha(n)), where \alpha is the inverse Ackermann function. That function grows so slowly that \alpha(n) < 5 for any n that could ever be stored in the observable universe. So treat it as constant, while knowing it technically is not. Using only one of the two optimisations gives O(\log n); using neither gives O(n).

What union-find can and cannot do.

Can: tell you whether two things are connected, count the groups, detect whether adding an edge closes a cycle, all while edges are being added, in near-constant time.

Cannot: remove an edge. The structure only merges. Undoing a union means rebuilding, because the trees have already been flattened and there is no record of which merge created which link. Problems that delete edges are usually solved by processing the whole thing backwards in time, adding edges instead of removing them.

Cannot: tell you the path between two elements, only that one exists.

Where it is genuinely used: Kruskal's MST below, detecting cycles while adding edges, image segmentation, grouping equivalent items (the "accounts merge" family of problems), and the classic percolation model in physics.

4. Minimum spanning trees: connect everything, as cheaply as possible

Given a connected undirected weighted graph, a spanning tree is a subset of edges that touches every vertex with no cycles — exactly V-1 edges. A minimum spanning tree is the one whose total weight is smallest.

The real question it answers: lay cable to every building, or lay fibre between every data centre, at minimum cost. Note it is not the shortest-path problem — an MST minimises the total wiring, not the distance between any particular pair, and the MST path between two vertices can be much longer than their shortest path.

Kruskal's algorithm — sort all edges by weight and add each one unless it would create a cycle.

function kruskal(n: number, edges: [number, number, number][]): number {
  edges.sort((a, b) => a[2] - b[2]);                         // (1)  O(E log E)
  const uf = new UnionFind(n);
  let total = 0, used = 0;
  for (const [a, b, w] of edges) {
    if (uf.union(a, b)) {                                    // (2)  false means it would cycle
      total += w;
      if (++used === n - 1) break;                           // (3)
    }
  }
  return used === n - 1 ? total : Infinity;                  // (4)
}

1. Cheapest first. This sort dominates the runtime.
2. Union-find is what makes this work. union returns false when both ends are already in the same group, which is precisely the definition of "adding this edge closes a cycle".
3. A spanning tree of n vertices has exactly n−1 edges, so once you have that many you are done and can stop early.
4. Fewer than n−1 means the graph was not connected in the first place.

O(E \log E), dominated by the sort.

Prim's algorithm — grow one tree outward, always adding the cheapest edge that reaches a vertex not yet in the tree. This uses the heap from Chapter 4.16 as its engine, and it is O(E \log V) with a binary heap.

Which to use: Kruskal for sparse graphs, because sorting E edges is cheap when E is small; Prim for dense graphs, because it never sorts and its cost scales with the heap operations instead. In interviews Kruskal is usually the faster one to write correctly, because union-find is short and the "does this close a cycle" question is answered for you.

Why greedy is correct here, which is a real follow-up: the cut property says that for any way of splitting the vertices into two groups, the cheapest edge crossing that split is in some minimum spanning tree. Both algorithms only ever add a cheapest-crossing edge — Kruskal across the split between "connected so far" and everything else, Prim across the split between the tree and the rest — so neither can make a choice it has to regret. Chapter 4.25 covers the general shape of this argument, and Chapter 1.8's Huffman coding uses the same kind of proof.

What the interviewer will push on

"Detect a cycle in a directed graph." The tell is three states, not two. Grey means "on the current recursion stack, so reaching it is a back edge and a cycle"; black means "finished in an earlier branch, which is fine". Candidates who use a plain visited set report false cycles on any diamond-shaped dependency, and the interviewer will hand you exactly that graph.

"Is the topological order unique?" No. Any vertex with in-degree zero may go next, so a graph with several such vertices has several valid orders. It is unique only when at every step exactly one vertex has in-degree zero, which happens exactly when the graph contains a path visiting every vertex.

"How do you detect a cycle with Kahn's algorithm?" You do not need to. If the output is shorter than the vertex count, the leftover vertices are in cycles, because a cycle's members can never reach in-degree zero. Getting the failure detection for free is the point.

"What is the complexity of union-find?" O(\alpha(n)) amortized with both path compression and union by size, effectively constant, but say both optimisations — with only one it is O(\log n) and with neither it is O(n). Then mention the limitation: it cannot undo a union.

"Is the minimum spanning tree the same as the shortest paths from a vertex?" No, and the difference is worth stating plainly: an MST minimises the total weight of all chosen edges, while a shortest-path tree minimises the distance from one source to each vertex. A three-vertex triangle with weights 1, 1 and 1.9 shows it — the MST takes the two 1-edges, and the shortest path between the two endpoints of the 1.9 edge is 1.9 directly, not 2 via the middle.

One thing to volunteer: mention that everything in Kahn's queue at the same time can run in parallel, so the number of queue rounds is the minimum wall-clock time with unlimited workers. That takes the answer from an algorithm to a system design, which is where the topic actually lives.

Recall

• A topological order exists if and only if the graph is a DAG, so the sorting algorithm is also the cycle detector.
• Kahn's algorithm counts in-degrees, starts from every zero, and decrements dependents; a short output means a cycle. Items in the queue together can run in parallel.
• DFS topological sort pushes in post-order then reverses, and needs three states — grey (on the stack, so a repeat is a back edge and a cycle) versus black (finished elsewhere, which is fine).
• Undirected cycle detection must skip the immediate parent edge, not all visited neighbours.
• Union-find keeps each group as a tree identified by its root; with path compression and union by size together it is effectively constant time. It cannot undo a union and cannot give you a path.
• A minimum spanning tree has exactly V−1 edges and minimises total weight — not the same as shortest paths. Kruskal sorts edges and uses union-find to reject cycles; Prim grows one tree with a heap.

Self-test: Why does a two-state visited set report false cycles in directed cycle detection? · How does Kahn's algorithm detect a cycle without a separate pass? · What breaks if union-find skips union-by-size? · Give a three-vertex example where the MST is not the shortest-path tree · What does union returning false tell Kruskal's algorithm?

Next: 4.19.3 handles weighted edges, where BFS's "fewest hops" answer stops being the cheapest one — Dijkstra, Bellman-Ford, Floyd-Warshall and A*, with the exact condition each one requires.