Minimum spanning tree: Prim, Kruskal and union-find

You are laying cable on a campus. There is a cost between every pair of buildings. You want to connect all the buildings to each other, but with the least cable. The answer is the minimum spanning tree (MST): the set of edges that contains all vertices, has no cycle and has the smallest total weight. Both algorithms of this week are greedy. Exam and quiz questions are almost always tracing questions: “write the edges Kruskal accepts in order”, “start Prim from A, give the order”, “what is the MST weight?”, “show the union-find array”.

Golden rules:

1. An MST has exactly V − 1 edges. Fewer does not connect, more forms a cycle.
2. Kruskal selects edges: start from the lightest edge, take it if it does not form a cycle.
3. Prim grows a vertex set: a single tree, add the vertex that connects to it most cheaply at each step.
4. Prim’s table is like Dijkstra’s but does not keep the path total, it keeps only the weight of a single edge.
5. The cycle check is done with union-find: if the two ends are in the same set, reject.

Definition and two properties

Spanning tree: a subgraph of a connected, undirected graph that contains all its vertices and has no cycle. V−1 edges for V vertices. The minimum one is the one with the smallest sum of edge weights.

The correctness of all MST algorithms rests on two properties:

• Cut property: Divide the vertices into any two groups. Of the edges that cross between the two groups, the lightest (if unique) is in every MST.
• Cycle property: The heaviest edge in a cycle (if unique) is in no MST.

Prim uses the cut property directly (cut = tree / the rest). Kruskal uses the fact that every edge it rejects is the heaviest edge of a cycle.

The working graph

Graph G (undirected). The edges sorted by weight:

edge   weight       edge   weight
A-C    1            B-C    7
C-D    2            C-E    8
A-B    3            D-F    9
D-E    4            B-E    10
B-D    5
E-F    6

Kruskal’s algorithm

1. Sort the edges by increasing weight (listing order on ties).
2. Each vertex starts in its own set.
3. For the next edge (u, v): if find(u) != find(v), accept the edge and union(u, v). Otherwise reject it (it forms a cycle).
4. Stop when V−1 edges have been accepted.

edge   decision  sets afterwards
A-C 1  ACCEPT    {A,C} {B} {D} {E} {F}
C-D 2  ACCEPT    {A,C,D} {B} {E} {F}
A-B 3  ACCEPT    {A,B,C,D} {E} {F}
D-E 4  ACCEPT    {A,B,C,D,E} {F}
B-D 5  REJECT    B and D are in the same set
E-F 6  ACCEPT    {A,B,C,D,E,F} → 5 edges, stop

The program’s parent array (in the order A..F, each element is the parent of that vertex):

  A-C 1 ACCEPT parent [A B A D E F]
  C-D 2 ACCEPT parent [A B A A E F]
  A-B 3 ACCEPT parent [A A A A E F]
  D-E 4 ACCEPT parent [A A A A A F]
  B-D 5 reject parent [A A A A A F]
  E-F 6 ACCEPT parent [A A A A A A]
Kruskal total 16 edges 5

The MST:

    B
    | 3
    A
    | 1
    C
    | 2
    D
    | 4
    E
    | 6
    F

In this example the MST came out as a chain; it is not always like this.

PITFALL · trying to check the remaining edges too. Stop when the 5th edge is accepted. Edges like B-C 7, C-E 8 would form cycles anyway; do not waste time extending the table needlessly in the exam. But if the question says “list all rejected edges”, write the rest as rejected too.

Union-find (disjoint set)

The cycle check of Kruskal is made fast with this structure. Each set is a tree; parent[x] is the parent of x, and at the root parent[r] = r.

• find(x): go up to the root, return the root.
• union(a, b): find the two roots, attach one under the other.

Two improvements:

• Union by size (or rank): attach the root of the smaller tree under the larger one. The height of the tree does not exceed $O(\log n)$.
• Path compression: during find, attach every node on the path directly to the root. The following finds take one step.

Together they give practically constant time per operation ($O(\alpha(n))$, inverse Ackermann).

Trace: union by size on 0..7

Rule: if the sizes are equal, the root of the second argument goes under the first.

  union(0,1) parent [0, 0, 2, 3, 4, 5, 6, 7]
  union(2,3) parent [0, 0, 2, 2, 4, 5, 6, 7]
  union(4,5) parent [0, 0, 2, 2, 4, 4, 6, 7]
  union(6,7) parent [0, 0, 2, 2, 4, 4, 6, 6]
  union(0,2) parent [0, 0, 0, 2, 4, 4, 6, 6]
  union(4,6) parent [0, 0, 0, 2, 4, 4, 4, 6]
  union(0,4) parent [0, 0, 0, 2, 0, 4, 4, 6]

     before               after find(7)
       0                       0
     / | \                / / | \ \
    1  2  4              1 2  4  6 7
       |  | \              |  |
       3  5  6             3  5
             |
             7

  path from 7 before find: 7 6 4 0
  find(7) = 0 parent after [0, 0, 0, 2, 0, 4, 0, 0]

PITFALL · path compression changes only those on the path. After find(7), 6 and 7 were attached to the root. 3 and 5 were not on the path, and their parents (2 and 4) did not change.

Prim’s algorithm

1. The starting vertex has value 0, the others ∞.
2. From those not in the tree, choose the vertex with the smallest value and add it to the tree (the smaller label on a tie).
3. For each neighbor u of the new vertex: if w(v,u) < d[u] then d[u] = w(v,u), from[u] = v.
4. Repeat until all vertices are added.

The only difference from Dijkstra is in step 3: Dijkstra compares d[v] + w, Prim compares only w. Prim’s d[u] value is “the cheapest edge to connect u to the tree”, not the distance from a source.

Starting from A in G (* is in the tree):

add   A   B   C   D   E   F    edge
A     0*  3   1   ∞   ∞   ∞    -
C     0*  3   1*  2   8   ∞    A-C 1
D     0*  3   1*  2*  4   9    C-D 2
B     0*  3*  1*  2*  4   9    A-B 3
E     0*  3*  1*  2*  4*  6    D-E 4
F     0*  3*  1*  2*  4*  6*   E-F 6

Prim order A C(via A-C 1) D(via C-D 2) B(via A-B 3) E(via D-E 4) F(via E-F 6) total 16

The same MST, a different order of addition. If you had started from F, the order would be F, E, D, C, A, B, but the edges and the total of 16 would be the same.

TIP · Prim or Kruskal? In a sparse graph, and when an edge list is given, Kruskal is practical. In a dense graph (adjacency matrix) the $O(V^2)$ version of Prim is good. Write the order of whichever the exam asks for; do not mix the two.

Is the MST unique?

If all edge weights are distinct, the MST is unique. If there are equal weights, there can be more than one MST, but the total of all of them is the same.

Graph H: P-Q 2, P-R 3, Q-R 2, Q-S 4, R-S 4, R-T 5, S-T 1.

  S-T 1 ACCEPT
  P-Q 2 ACCEPT
  Q-R 2 ACCEPT
  P-R 3 reject
  Q-S 4 ACCEPT
Kruskal total 9 edges 4

If R-S (which is also 4) were taken instead of Q-S, {P, Q, R} and {S, T} would still be connected and the total would again be 9. There are two valid MSTs.

Quiz rehearsal

In a quiz, usually a single graph is given for 15-20 minutes and three things are asked. Try yourself against the clock (graph G):

1) The edges Kruskal accepts, in order?
2) The order of addition if Prim starts from B?
3) The MST weight?
answers:
1) A-C, C-D, A-B, D-E, E-F
2) B, A(3), C(1), D(2), E(4), F(6)
3) 16

Checking answer 2: from B, A=3, D=5, C=7, E=10. A is added, C becomes 1. C is added, D=2, E=8. D is added, E=4, F=9. E is added, F=6. Do not do it without drawing the table on paper; the most common mistake when going from memory is to pick D=5 when starting from B.

Complexity summary

Common mistakes

add   A  B  C  D  E  F
A     0* 3  1  ∞  ∞  ∞
C     0* 3  1* 2  8  ∞
D     0* 3  1* 2* 4  9
B     0* 3* 1* 2* 4  9
E     0* 3* 1* 2* 4* 6
F     0* 3* 1* 2* 4* 6*

        0
      / | \
     1  2  4
        |  | \
        3  5  6
              |
              7

static int[] parent, size;
static int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);   // path compression
    return parent[x];
}
static boolean union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return false;        // same set: cycle
    if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
    parent[rb] = ra;                   // the smaller goes under the larger
    size[ra] += size[rb];
    return true;
}

static int kruskal(int n, int[][] edges) {
    parent = new int[n];
    size = new int[n];
    for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
    int[][] es = edges.clone();
    Arrays.sort(es, (x, y) -> Integer.compare(x[2], y[2]));
    int total = 0, used = 0;
    for (int[] e : es) {
        if (union(e[0], e[1])) {
            total += e[2];
            if (++used == n - 1) break;
        }
    }
    return total;
}