Minimum Spanning Trees and Prim’s Algorithm Revision Notes for AQA A-Level Further Maths

Minimum Spanning Trees and Prim's Algorithm

Introduction to Prim's algorithm

When we need to find a minimum spanning tree (MST) for a network, we have two main algorithms available: Kruskal's algorithm and Prim's algorithm. While both achieve the same goal, Prim's algorithm is particularly useful when working with networks stored as distance matrices.

infoNote

A minimum spanning tree is a connected subgraph that includes all vertices in the network whilst having the minimum possible total weight. It contains no cycles and uses exactly $n-1$ edges for a network with $n$ vertices.

Why use Prim's algorithm?

chatImportant

Kruskal's algorithm is difficult to adapt for computerisation when the network is stored as a matrix. This is because checking whether an arc will form a cycle with already chosen arcs is complex in matrix form. Prim's algorithm avoids this problem entirely, making it better suited for computer implementation.

Understanding Prim's algorithm

Prim's algorithm is a greedy algorithm. This means it makes the locally optimal choice at each step, selecting the smallest weight arc available at that moment. The algorithm builds the MST by growing outward from a starting vertex, adding one vertex at a time to the connected set.

infoNote

The key advantage of being greedy is that it avoids forming cycles. The algorithm only considers arcs connecting the connected set to unconnected vertices, so cycles cannot possibly form.

Prim's algorithm on graphs

When working directly with a drawn network, follow these steps:

Step 1: Select any vertex to start your connected set.

Step 2: Examine all arcs that connect a vertex in the connected set to a vertex not yet in the set. Choose the arc with the smallest weight. Add this arc to your spanning tree and add the new vertex to the connected set.

Step 3: If unconnected vertices remain, return to Step 2. Otherwise, the spanning tree is complete.

chatImportant

Handling Equal Weights

If multiple arcs have the same minimum weight at any stage, you may choose any one of them at random. This can result in different (but equally valid) minimum spanning trees with the same total weight.

Worked example 1: Graph method

Let's find the minimum spanning tree for the following network, starting from vertex $A$ .

lightbulbExample

Worked Example: Finding the MST Using the Graph Method

We'll build the MST step by step, showing which vertices are connected at each stage.

Step 1: Start with vertex $A$ in the connected set.

Available arcs from $A$ : $AB$ (weight 11), $AC$ (weight 10), $AD$ (weight 8)
Minimum weight: $AD = 8$
Add arc $AD$ to the MST

Step 2: Connected set: ${A, D}$

Available arcs: $AB$ (11), $AC$ (10), $DC$ (5), $DE$ (10), $DF$ (10)
Minimum weight: $DC = 5$
Add arc $DC$ to the MST

Step 3: Connected set: ${A, C, D}$

Available arcs: $AB$ (11), $CB$ (7), $CE$ (8), $CF$ (4), $DE$ (10), $DF$ (10)
Minimum weight: $CF = 4$
Add arc $CF$ to the MST

Step 4: Connected set: ${A, C, D, F}$

Available arcs: $AB$ (11), $CB$ (7), $CE$ (8), $DE$ (10), $FE$ (5)
Minimum weight: $FE = 5$
Add arc $FE$ to the MST

Step 5: Connected set: ${A, C, D, E, F}$

Available arcs: $AB$ (11), $CB$ (7), $EB$ (9)
Minimum weight: $CB = 7$
Add arc $CB$ to the MST

Conclusion:

The MST consists of arcs: $AD$ , $DC$ , $CF$ , $FE$ , $CB$
Total weight: $8 + 5 + 4 + 5 + 7 = 29$

infoNote

Exam tip: Always list the arcs in the order you choose them, and clearly state the total weight of your MST.

Prim's algorithm on matrices

When the network is given as a distance matrix, you don't need to draw the graph. The algorithm can be applied directly to the matrix using the following procedure.

Step 1: Select the first vertex.

Step 2: Cross out the row for the chosen vertex and number its column. The column number shows the order in which vertices are added to the connected set.

Step 3: Find the minimum undeleted weight in the numbered columns. Circle this value. The row containing this value indicates the next vertex to add.

Step 4: Repeat Steps 2 and 3 until all vertices have been chosen.

chatImportant

Handling Equal Weights in Matrices

If two or more cells contain equal minimum weights, choose one at random.

Worked example 2: Matrix method

Use Prim's algorithm to find the minimum spanning tree for the network given by this distance matrix:

lightbulbExample

Worked Example: Finding the MST Using the Matrix Method

We'll work through the algorithm step by step, showing the matrix at each stage.

Initial setup: Choose vertex $A$ as the starting vertex.

Iteration 1:

Cross out row $A$ and label column $A$ with "1"
In column $A$ , the minimum undeleted weight is 9 (in row $C$ )
Circle the 9
Next vertex: $C$

	1
	$A$	$B$	$C$	$D$	$E$	$F$
$A$	-	12	9	-	14	-
$B$	12	-	-	7	-	10
$C$	9	-	-	6	8	-
$D$	-	7	6	-	-	8
$E$	14	-	8	-	-	9
$F$	-	10	-	8	9	-

Iteration 2:

Cross out row $C$ and label column $C$ with "2"
In columns $A$ and $C$ , the minimum undeleted weight is 6 (in row $D$ , column $C$ )
Circle the 6
Next vertex: $D$

Iteration 3:

Cross out row $D$ and label column $D$ with "3"
In columns $A$ , $C$ , and $D$ , the minimum undeleted weight is 7 (in row $B$ , column $D$ )
Circle the 7
Next vertex: $B$

Iteration 4:

Cross out row $B$ and label column $B$ with "4"
In columns $A$ , $B$ , $C$ , and $D$ , the minimum undeleted weight is 8 (tie between $CE$ and $DF$ )
Choose $CE$ at random (we could equally choose $DF$ )
Circle the 8 in row $E$ , column $C$
Next vertex: $E$

Iteration 5:

Cross out row $E$ and label column $E$ with "5"
In columns $A$ , $B$ , $C$ , $D$ , and $E$ , the minimum undeleted weight is 8 (in row $F$ , column $D$ )
Circle the 8
Next vertex: $F$

Iteration 6:

Cross out row $F$ and label column $F$ with "6"
All vertices are now in the connected set

Conclusion:

The minimum spanning tree consists of arcs: $AC$ , $CD$ , $DB$ , $CE$ , $DF$
Total weight: $9 + 6 + 7 + 8 + 8 = 38$

infoNote

Exam tip: When using the matrix method, always number the columns clearly to show the order of selection. This makes your working easy to follow and helps you avoid mistakes.

Real-world application

Prim's algorithm is particularly useful for solving practical problems involving network optimisation. Let's look at an example involving infrastructure upgrades.

Worked example 3: Country park paths

A country park has seven picnic sites and a car park connected by rough paths. The distances are shown in metres. The council plans to upgrade some paths to wheelchair-accessible standards at a cost of £55 per metre. We need to determine which paths should be upgraded so that all picnic sites are accessible from the car park, whilst minimising the total cost.

lightbulbExample

Worked Example: Optimising Path Upgrades

We'll apply Prim's algorithm starting from the car park, since visitors must be able to reach all sites from there.

Steps of the algorithm:

Starting from the car park:

First arc: From car park, available paths are to $A$ (200), $E$ (400), and $F$ (350). Minimum: Car park- $A$ = 200 m
Second arc: From the connected set {Car park, $A$ }, connect to $F$ (the second arc needed)
Third arc: $FE$ = 150 m
Fourth arc: $FG$ = 190 m
Fifth arc: $GB$ = 200 m
Sixth arc: $GC$ = 230 m
Seventh arc: $ED$ = 280 m

The spanning tree is complete with 8 vertices connected by 7 arcs.

Total length to upgrade: $200 + 150 + 190 + 200 + 230 + 280 = 1490 \text{ m}$

Cost calculation: $\text{Cost} = 1490 \times 55 = \text{£}81,950$

Answer in context: The council should upgrade the paths from the car park to $A$ , then $FE$ , $FG$ , $GB$ , $GC$ , and $ED$ at a total cost of £81,950. This ensures all picnic sites are wheelchair-accessible from the car park using the minimum length of upgraded path.

infoNote

Exam tip for contextual problems:

Always list the order in which you choose the arcs (or label columns if using a matrix)
State your final answer in the context of the question
Include appropriate units throughout your working

Comparison with Kruskal's algorithm

You may have previously learned Kruskal's algorithm for finding minimum spanning trees. Here are the key differences:

Aspect	Kruskal's algorithm	Prim's algorithm
Starting point	Considers all edges	Starts from one vertex
Growth pattern	Builds multiple fragments	Grows one connected tree
Best suited for	Small networks, graph form	Matrices, computerisation
Edge selection	Always picks global minimum	Picks minimum connecting to tree

infoNote

Both algorithms are greedy and both guarantee to find an MST with the same minimum total weight.

bookmarkSummary

Key Points to Remember:

Prim's algorithm builds a minimum spanning tree by starting from one vertex and growing the tree one vertex at a time.
It is a greedy algorithm that always chooses the minimum weight arc connecting the connected set to an unconnected vertex. This approach automatically avoids creating cycles.
When working with graphs, list the arcs in the order chosen. When working with matrices, cross out rows and number columns to show your progression.
If multiple arcs have equal minimum weights, you can choose any one at random. This may result in different MSTs, but they will all have the same minimum total weight.
Always show your working clearly in exams by listing arcs in order for graphs or numbering columns for matrices. State your final answer with the total weight and, for contextual problems, include appropriate units and explain the meaning.

Minimum Spanning Trees and Prim’s Algorithm (AQA A-Level Further Maths): Revision Notes