Minimum Spanning Trees
Learn Prim's and Kruskal's algorithms for finding minimum spanning trees, with step-by-step examples and real-world applications in HSC Advanced Mathematics.
What is a Spanning Tree?
A spanning tree of a connected graph is a subgraph that connects all vertices using the minimum number of edges, with no cycles. For a graph with n vertices, a spanning tree has exactly n − 1 edges.
Spanning tree properties:
1. Connects all vertices in the graph.
2. Contains exactly n − 1 edges (where n = number of vertices).
3. Contains no cycles (is a tree).
A minimum spanning tree (MST) is a spanning tree whose total edge weight is as small as possible. It represents the cheapest way to connect all vertices.
Real-world example: A council needs to connect 6 towns with roads. The MST finds the set of roads with minimum total distance that ensures every town is reachable from every other town.
A graph may have multiple spanning trees, but the MST has the minimum total weight.
Prim's Algorithm
Prim's algorithm builds the MST by starting from any vertex and repeatedly adding the cheapest edge that connects a vertex in the tree to a vertex not yet in the tree.
Steps of Prim's Algorithm:
1. Start with any vertex. Add it to the MST set.
2. Find the cheapest edge connecting a vertex in the MST to a vertex outside it.
3. Add that edge and the new vertex to the MST.
4. Repeat steps 2–3 until all vertices are included.
Key idea: Prim's grows the tree one vertex at a time from a starting point, always choosing the minimum weight edge to an unconnected vertex.
Kruskal's Algorithm
Kruskal's algorithm builds the MST by sorting all edges by weight and adding them one at a time, provided they don't create a cycle.
Steps of Kruskal's Algorithm:
1. Sort all edges in ascending order of weight.
2. Pick the edge with the smallest weight.
3. If adding it does not create a cycle, include it in the MST.
4. Repeat until n − 1 edges are selected.
Key difference from Prim's: Kruskal's considers edges globally (cheapest first), while Prim's grows from a single vertex.
Both algorithms always produce the same minimum total weight, though the tree itself may differ when edges have equal weights.
Key Vocabulary
Spanning Tree
A subgraph that connects all vertices with the minimum number of edges and contains no cycles.
Minimum Spanning Tree
A spanning tree with the smallest possible total edge weight.
Prim's Algorithm
Builds an MST by growing from a starting vertex, always adding the cheapest connecting edge.
Kruskal's Algorithm
Builds an MST by sorting all edges by weight and adding them if they don't create a cycle.
Worked Examples
Use Prim's algorithm starting from A. Edges: A–B(4), A–C(3), B–C(1), B–D(6), C–D(5), C–E(2), D–E(7).
Step 1: Start at A. Cheapest edge from A: A–C(3). MST = {A, C}.
Step 2: Cheapest edge from {A, C} to outside: C–B(1). MST = {A, C, B}.
Step 3: Cheapest from {A, C, B} to outside: C–E(2). MST = {A, C, B, E}.
Step 4: Cheapest from {A, C, B, E} to D: C–D(5). MST = {A, C, B, E, D}.
Answer: MST edges: A–C(3), C–B(1), C–E(2), C–D(5). Total weight = 11.
Use Kruskal's algorithm on the same graph from Example 1.
Step 1: Sort edges: B–C(1), C–E(2), A–C(3), A–B(4), C–D(5), B–D(6), D–E(7).
Step 2: Add B–C(1). No cycle. Add C–E(2). No cycle. Add A–C(3). No cycle.
Step 3: Skip A–B(4) — would create cycle A–B–C–A. Add C–D(5). No cycle.
Answer: MST edges: B–C(1), C–E(2), A–C(3), C–D(5). Total = 11. Same result!
A council needs to connect 4 towns (P, Q, R, S) with pipes. Costs: P–Q(8), P–R(5), P–S(10), Q–R(3), Q–S(7), R–S(6). Find the minimum cost.
Using Kruskal's: Sorted: Q–R(3), P–R(5), R–S(6), Q–S(7), P–Q(8), P–S(10).
Add Q–R(3), P–R(5), R–S(6). We now have 3 edges connecting 4 vertices (n − 1 = 3).
Answer: Minimum cost = 3 + 5 + 6 = $14. Pipes: Q–R, P–R, R–S.
Knowledge Check
Select the correct answer for each question. Click "Check Answer" to see if you are right.
Question 1
A graph has 7 vertices. How many edges does its spanning tree have?
Question 2
In Kruskal's algorithm, when should you skip an edge?
Question 3
Edges: A–B(2), A–C(4), B–C(1), B–D(7), C–D(3). What is the total weight of the MST?
Question 4
What is the main difference between Prim's and Kruskal's algorithms?
Question 5
Which real-world problem is best modelled by a minimum spanning tree?
Key Concepts Summary
- ● A spanning tree connects all vertices with n − 1 edges and no cycles.
- ● A minimum spanning tree has the smallest possible total edge weight.
- ● Prim's algorithm grows the MST from a starting vertex, always adding the cheapest connecting edge.
- ● Kruskal's algorithm sorts all edges and adds them in order, skipping any that would create a cycle.
- ● Applications include network design, infrastructure planning, and telecommunications.