Minimum Spanning Trees

Suppose a town wants to connect seven buildings with fibre-optic cable so every building is linked to every other, directly or indirectly, using as little cable as possible. That is the minimum spanning tree problem. Two short, reliable algorithms solve it, Kruskal’s and Prim’s, and you’ll be expected to carry out both and show each choice.

Key ideas

Spanning trees

Recall that a tree is a connected graph with no cycles. A spanning tree of a connected graph $G$ is a subgraph that is a tree and includes every vertex of $G$. If $G$ has $n$ vertices, every spanning tree has exactly $n - 1$ edges.

In a weighted graph, a minimum spanning tree (MST) is a spanning tree whose total weight is as small as possible. It never contains a cycle, because you could always drop the heaviest edge of a cycle and stay connected.

Kruskal’s algorithm

1. List the edges in order of weight, smallest first.
2. Go down the list. Add each edge unless it would make a cycle with the edges already chosen; if it would, reject it.
3. Stop when you have $n - 1$ edges.

Kruskal’s picks the cheapest edges anywhere in the graph, so the chosen edges can be in separate pieces until they join up at the end.

Prim’s algorithm

1. Choose any starting vertex.
2. Look at every edge joining a vertex already in the tree to a vertex not yet in the tree. Add the one with the smallest weight.
3. Repeat until every vertex is in the tree.

Prim’s grows a single tree outward from the start, so it never needs a cycle check: an edge to a new vertex can’t make a cycle.

Prim’s algorithm on a table (the matrix method)

When the graph is given as a weighted adjacency table, Prim’s can be done on the table itself:

1. Choose a starting vertex. Cross out its row, and label its column with $1$.
2. In all the labelled columns, find the smallest entry that hasn’t been crossed out. Circle it. That edge joins the tree to the vertex of that entry’s row.
3. Cross out that vertex’s row, and label its column with the next number.
4. Repeat steps 2 and 3 until every column is labelled. The circled entries are the MST edges.

Crossing out rows stops you from choosing an edge to a vertex that’s already in the tree.

Do Kruskal’s and Prim’s give the same tree?

Both algorithms always give a tree of the same minimum total weight. If all the edge weights are different, the MST is unique, so both find exactly the same tree. When some weights are equal, there may be several MSTs with the same total, and the two algorithms (or different starting vertices) might find different ones.

Worked examples

The weighted graph used in Examples 1 and 2.

Example 1: Kruskal’s algorithm

Use Kruskal’s algorithm to find a minimum spanning tree for the graph above. State its total weight.

Solution. There are $7$ vertices, so the tree needs $6$ edges. Work down the edges in order of weight:

Edge	Weight	Decision
CF	3	Add
AD	4	Add
BE	5	Add
BD	6	Add
FG	6	Add
AB	7	Reject (makes cycle A–B–D–A)
EG	7	Add: that’s $6$ edges, so stop

(BD and FG tie at $6$, and AB and EG tie at $7$; you can take either first and get the same result.)

The MST is CF, AD, BE, BD, FG, EG, with total weight

$$3 + 4 + 5 + 6 + 6 + 7 = 31$$

The minimum spanning tree (blue) has total weight $31$.

Example 2: Prim’s algorithm

Use Prim’s algorithm, starting at A, on the same graph. Show the order in which edges are chosen.

Solution. At each step, list the edges from the tree to new vertices and pick the smallest.

Step	Tree so far	Cheapest edges to new vertices	Chosen
1	A	AB 7, AD 4	AD 4
2	A, D	AB 7, BD 6, DE 10, DG 12	BD 6
3	A, D, B	BC 9, BE 5, DE 10, DG 12	BE 5
4	A, D, B, E	BC 9, CE 8, EF 11, EG 7, DG 12	EG 7
5	A, D, B, E, G	BC 9, CE 8, EF 11, FG 6	FG 6
6	A, D, B, E, G, F	BC 9, CE 8, CF 3	CF 3

The edges in order are AD, BD, BE, EG, FG, CF, with total weight $4 + 6 + 5 + 7 + 6 + 3 = 31$. It’s the same tree as Kruskal’s. That’s expected here: the tied weights never give a choice between two different trees, so this graph has only one MST.

Example 3: Prim’s matrix method

The table shows the lengths, in km, of possible pipelines between five sites. Use Prim’s algorithm, starting at P, to find the minimum total length of pipeline that connects all five sites.

	P	Q	R	S	T
P	–	8	5	–	9
Q	8	–	4	7	–
R	5	4	–	6	10
S	–	7	6	–	3
T	9	–	10	3	–

Solution. Follow the matrix method:

• Cross out row P and label column P with $1$. Smallest entry left in column P: $5$ (row R). Circle PR $= 5$.
• Cross out row R; label column R with $2$. In columns P and R, the uncrossed entries are Q $8$, T $9$ (column P) and Q $4$, S $6$, T $10$ (column R). Smallest: $4$ in row Q. Circle RQ $= 4$.
• Cross out row Q; label column Q with $3$. Uncrossed entries in columns P, R, Q: T $9$; S $6$, T $10$; S $7$. Smallest: $6$ in row S. Circle RS $= 6$.
• Cross out row S; label column S with $4$. Uncrossed entries: T $9$, T $10$, and T $3$ in column S. Smallest: $3$. Circle ST $= 3$.

Every column is now labelled. The MST is PR, RQ, RS, ST, with total length

$$5 + 4 + 6 + 3 = 18 \text{ km}$$

Example 4: When there are ties

A graph has edges AB $4$, BC $4$, CA $4$ and CD $2$. Find the weight of a minimum spanning tree. Is the MST unique?

Solution. Kruskal’s: take CD $2$, then any two of the three edges of weight $4$ (the third would complete the triangle A–B–C). The total is $2 + 4 + 4 = 10$.

The MST is not unique: three different trees (CD with AB and BC, CD with AB and CA, or CD with BC and CA) all have weight $10$. Different algorithms or starting points might pick different ones, but the minimum total is always $10$.

Common mistakes

Adding an edge that makes a cycle in Kruskal’s. Before you add each edge, check whether its two ends are already connected through edges you’ve chosen. If they are, reject it.

Choosing the cheapest edge from the newest vertex only in Prim’s. At each step, look at edges from every vertex already in the tree, not just the last one added. (In Example 2, step 4 compares edges from A, D, B and E.)

Stopping too early or too late. A spanning tree on $n$ vertices has exactly $n - 1$ edges. Count them.

Reading the table the wrong way in the matrix method. Search the labelled columns, and the new vertex is the row of the circled entry. Cross out rows of vertices already in the tree so you never circle an edge back into the tree.

Not showing the order of choices. IB questions usually ask you to show the algorithm. List the edges in the order chosen (and rejections for Kruskal’s), not just the final tree.

Confusing an MST with a shortest route. The MST connects all vertices as cheaply as possible; it is not the shortest path between two particular vertices, and not a route you could drive in one go.

Practice

1. (Warm-up) A graph has edges AB $3$, AC $5$, BC $4$, BD $6$, CD $2$, CE $7$ and DE $8$. Use Kruskal’s algorithm to find a minimum spanning tree and its weight.

Solution

In order: CD $2$ add, AB $3$ add, BC $4$ add, AC $5$ reject (cycle A–B–C–A), BD $6$ reject (cycle B–C–D–B), CE $7$ add. That’s $4$ edges for $5$ vertices, so stop.

MST: CD, AB, BC, CE, with weight $2 + 3 + 4 + 7 = 16$.

2. (Warm-up) A connected graph has $9$ vertices and $15$ edges. How many edges are in a spanning tree? How many edges of the graph are not used?

Solution

A spanning tree on $9$ vertices has $9 - 1 = 8$ edges, so $15 - 8 = 7$ edges are not used.

3. (Warm-up) Explain why Prim’s algorithm never creates a cycle.

Solution

Each step adds an edge from a vertex already in the tree to a vertex not yet in the tree. A cycle needs an edge joining two vertices that are already connected, and Prim’s never adds one of those.

4. (Core) Use Prim’s algorithm, starting at A, to find a minimum spanning tree for the complete graph given by this table. Show the order in which edges are added.

	A	B	C	D	E
A	–	14	9	17	12
B	14	–	11	8	15
C	9	11	–	13	10
D	17	8	13	–	16
E	12	15	10	16	–

Solution

• From A: the smallest entry in column A is $9$ (C). Add AC $9$.
• From A, C: candidates B $14$, D $17$, E $12$ (column A) and B $11$, D $13$, E $10$ (column C). Add CE $10$.
• From A, C, E: smallest is $11$ (C to B). Add CB $11$.
• From A, C, E, B: smallest to D is $8$ (B to D). Add BD $8$.

Order: AC, CE, CB, BD. Total weight $9 + 10 + 11 + 8 = 38$.

5. (Core) Use Prim’s algorithm on the graph in the first figure, starting at G. List the edges in the order they’re added, and check the total.

Solution

• From G: GD $12$, GE $7$, GF $6$. Add FG $6$.
• From G, F: CF $3$ is smallest. Add CF $3$.
• From G, F, C: GD $12$, GE $7$, EF $11$, CE $8$, BC $9$. Add EG $7$.
• From G, F, C, E: BE $5$ is smallest. Add BE $5$.
• From G, F, C, E, B: BD $6$, AB $7$, DE $10$, DG $12$. Add BD $6$.
• Last: AD $4$ (smaller than AB $7$). Add AD $4$.

Order: FG, CF, EG, BE, BD, AD. Total $6 + 3 + 7 + 5 + 6 + 4 = 31$, the same tree as Examples 1 and 2.

6. (Core) Six villages K, L, M, N, O, P are to be linked by fibre-optic cable. Possible cable routes, in km, are KL $4$, KM $6$, LM $3$, LN $7$, MN $5$, MO $8$, NO $4$, NP $6$ and OP $5$. Cable costs $15 000 per km to lay. Use Kruskal’s algorithm to find the minimum cost of linking all six villages.

Solution

In order: LM $3$ add, KL $4$ add, NO $4$ add, MN $5$ add, OP $5$ add. That’s $5$ edges for $6$ villages, so stop. (KM $6$, NP $6$, LN $7$ and MO $8$ would each make a cycle anyway.)

Total length: $3 + 4 + 4 + 5 + 5 = 21$ km.

Cost: $21 \times 15\,000 = 315\,000$, so the minimum cost is $315 000.

7. (Core) In the graph in the first figure, the edge DG must be included in the network (for example, a cable that already exists). Find the minimum total weight of a spanning tree that includes DG.

Solution

Start with DG $12$ already chosen, then apply Kruskal’s to the rest: CF $3$ add, AD $4$ add, BE $5$ add, BD $6$ add, FG $6$ add. Now all $7$ vertices are connected with $6$ edges (D and G were joined at the start, and FG links C and F to them), so stop. EG $7$ is no longer needed: it would make the cycle E–B–D–G–E.

Total: $12 + 3 + 4 + 5 + 6 + 6 = 36$.

8. (Challenge) In Example 3, a sixth site U is added. The only possible pipelines to U are UP $2$ km and UT $4$ km. Find the new minimum total length, and explain why adding a site didn’t increase it.

Solution

Kruskal’s on the new graph: UP $2$ add, ST $3$ add, QR $4$ add, UT $4$ add, PR $5$ add. Now all $6$ sites are connected with $5$ edges, so stop. (RS $6$ would make the cycle R–S–T–U–P–R.)

New total: $2 + 3 + 4 + 4 + 5 = 18$ km, the same as before.

The new site gives a cheaper way to link the two halves of the network: P–U–T costs $2 + 4 = 6$, and it replaces RS (also $6$). So the extra vertex adds two edges but lets you drop one, and the total stays at $18$ km.

9. (Challenge) In the graph in the first figure, the weight of edge CE is changed from $8$ to $w$. For which values of $w$ is CE in every minimum spanning tree?

Solution

In the current MST, C and E are joined by the tree path C–F–G–E, with edges $3$, $6$ and $7$. If CE is added, it forms a cycle with this path. CE belongs in the MST exactly when it is cheaper than the heaviest edge on that cycle that it could replace, which is EG $7$.

• If $w \lt 7$: swap EG for CE and the total drops, so CE is in every MST (the new total is $24 + w$).
• If $w = 7$: CE and EG tie, so there are two MSTs, one with CE and one without.
• If $w \gt 7$: CE is not in the MST.

So CE is in every MST when $w \lt 7$.