Prim's Algorithm (Edexcel A Level Further Maths): Revision Note
Introduction to Prim's Algorithm
What is Prim's algorithm?
Prim's algorithm is another method of finding the minimum spanning tree in a network
It can be used when the information for a network is given as a graph or in a matrix
Prim's Algorithm using Edges & Vertices
What are the steps in Prim’s Algorithm when using a graph?
Prim’s algorithm involves adding edges from vertices that are already connected to the tree.
Cycles are avoided by only adding edges that are not already connected at one end.
STEP 1 Start at any vertex and choose the edge of least weight that is connected to it
STEP 2 Choose the edge of least weight that is incident (connected) to any of the vertices already connected and does not connect to another vertex that is already in the tree
If there is a choice of the edges of equal weight, either can be selected
STEP 3 Repeat STEP 2 until all of the vertices are added to the tree
Worked Example
Consider the network, G, below.
a) Using Prim’s algorithm, find the minimum spanning tree.
STEP 1
Select a starting vertex (A) and choose the edge of least weight that is connected to it
AB (15)
STEP 2
Select the next edge of least weight that is incident (connected) to either of the vertices already in the tree
AB (15), BC (13)
STEP 3 Continue to select the edge of least weight that is incident to any of the other vertices that are already connected to the tree
AB (15), BC (13), CE (12)
Remember to record the order in which the edges were added
Edges added in the order: AB (15), BC (13), CE (12), BD (17)
b) State the total weight of the minimum spanning tree.
Add up the weight of the edges in the minimum spanning tree.
15 + 13 + 12 + 17 = 57
Total weight = 57
Prim's Algorithm using a Matrix
How do you apply Prim’s algorithm to a matrix?
A minimum spanning tree is built up from the least weight edges that are incident to vertices already in the tree by looking at the relevant rows in the distance matrix
STEP 1
Select any vertex to start from, cross out the values in the column associated with that vertex and label the row associated with the vertex 1STEP 2
Circle the lowest value in any cell along that row and add the edge to your tree, cross out the remaining values in the column of the cell that you have circledSTEP 3
Label the row associated with the same vertex as the column in the previous STEP with the next numberSTEP 4
Circle the lowest value in any cell along any of the rows that have been labelled and add the edge to your tree, cross out the remaining values in the column of the cell that you have circledSTEP 5
Repeat STEPS 3 and 4 until all vertices have been added to the tree
Some versions of Prim's algorithm using a matrix will cross out rows and label columns
Examiner Tips and Tricks
Look out for questions that ask you to minimise the cost or length etc. from a network – they are implying that they want you to find the minimum spanning tree!
Be careful not to confuse Prim's algorithm with the Nearest Neighbour algorithm!
Worked Example
The adjacency matrix of a network, is shown below.
| A | B | C | D | E |
A | - | 15 | 22 | 18 | 25 |
B | 15 | - | 13 | 17 | 24 |
C | 22 | 13 | - | 30 | 12 |
D | 18 | 17 | 30 | - | 21 |
E | 25 | 24 | 12 | 21 | - |
a) Starting from vertex A, use Prim’s algorithm on the table to find and draw the minimum spanning tree. Show each step of the process clearly.
STEP 1
Start at the row for vertex A and label it 1 Cross out the values in column A
STEP 2
Circle the edge of least weight in row 1 and record which edge it is
Delete the remaining values in column B
AB (15)
STEP 3
Label the row for vertex B, 2STEP 4
Circle the edge of least weight in row 1 and row 2, remembering to record the edge Cross out the remaining values in the column of that circled edge
AB (15), BC (13)
STEP 5
Repeat Steps 3 and 4 until all vertices are added
STEP 3
Label the row for vertex C, 3STEP 4
Circle the edge of least weight in rows 1 to 3, remembering to record the edge
Delete the remaining values in column E
AB (15), BC (13), CE (12)
STEP 3
Label the row for vertex E, 4STEP 4
Circle the edge of least weight in rows 1 to 4, remembering to record the edge Delete the remaining values in column D
AB (15), BC (13), CE (12), DE (17)
All vertices have been selected
You should have a list of the order in which the edges were selected
Edges added in the order: AB (15), BC (13), CE (12), BD (17)
b) State the lowest cost of connecting all of the buildings to the electricity supply.
Add up the weights of the edges in the minimum spanning tree.
15 + 13 + 12 + 17 = 57
Total weight = 57
You've read 0 of your 5 free revision notes this week
Sign up now. It’s free!
Did this page help you?