D1.2.1 The minimum spanning tree (minimum connector) problem. Prim’s and…

Section
D1.2 Algorithms on graphs
Level
AS & A level
Statement
The minimum spanning tree (minimum connector) problem. Prim’s and Kruskal’s algorithm.
Guidance
Matrix representation for Prim’s algorithm is expected. Drawing a network from a given matrix and writing down the matrix associated with a network may be required.
Since 2018
20 parts, 41 marks · topic pages: Minimum spanning trees (Prim, Kruskal) and shortest paths (Dijkstra, Floyd), Route inspection and the travelling salesman problem

Back to the checklist

June 2025 · AS Paper 2 (Decision 1) · Q1(b) 2 marks
B E A F C Figure 1 (b) Use Prim’s algorithm, starting at A, to find the minimum spanning tree for the network in Figure 1. You must list the arcs in the order in which you select them. (2)
June 2025 · AS Paper 2 (Decision 1) · Q1(c) 2 marks
(c) (i) Draw the minimum spanning tree on Diagram 1 in the answer book. (ii) Find the weight of the minimum spanning tree. (2)
June 2024 · Paper 3D (Decision 1) · Q2(a) 3 marks
2. The table below represents a network of shortest distances, in miles, to travel between nine castles, A, B, C, D, E, F, G, H and J. A B C E F G H J A – B – C – – E – F – G – H – J – (a) Use Prim’s algorithm, starting at D, to find the minimum spanning tree for this network. You must clearly state the order in which you select the arcs of your tree. (3)
June 2024 · Paper 3D (Decision 1) · Q2(b) 1 mark
(b) State the weight of the minimum spanning tree found in part (a). (1)
June 2024 · Paper 3D (Decision 1) · Q2(c) 1 mark
(c) Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book. (1)
June 2024 · Paper 3D (Decision 1) · Q2(d) 1 mark
A historian needs to visit all of the castles, starting and finishing at the same castle, and wishes to minimise the total distance travelled. (d) Use your answer to part (b) to calculate an initial upper bound for the length of the historian’s route. (1)
June 2024 · Paper 3D (Decision 1) · Q2(g) 2 marks
(g) By deleting A and all of its arcs, find a lower bound for the length of the historian’s route. (2)
June 2023 · AS Paper 2 (Decision 1) · Q3(c) 3 marks
(c) Use Prim’s algorithm, starting at C, to find a minimum spanning tree for the network. You must clearly state the order in which you select the edges of your tree. (3)
June 2023 · AS Paper 2 (Decision 1) · Q3(d) 1 mark
(d) State the total length, in km, of the minimum spanning tree. (1)
June 2023 · Paper 3D (Decision 1) · Q5(b) 3 marks
(b) Starting at A, use Prim’s algorithm to find the minimum spanning tree for the table of shortest distances. You must state the order in which you select the arcs of your tree. (3)
June 2023 · Paper 3D (Decision 1) · Q5(d) 2 marks
(d) By deleting G and all of its arcs, find a lower bound for the length of Pete’s route. (2)
June 2022 · AS Paper 2 (Decision 1) · Q1(b) 3 marks
C A F G E B Figure 1 (b) Use Kruskal’s algorithm to find the minimum spanning tree for the network in Figure 1. You should list the arcs in the order in which you consider them. For each arc, state whether or not you are adding it to your minimum spanning tree. (3)
June 2022 · AS Paper 2 (Decision 1) · Q1(c) 2 marks
(c) (i) Draw the minimum spanning tree on Diagram 1 in the answer book. (ii) State the total weight of the tree. (2)
Nov 2021 · Paper 3D (Decision 1) · Q3(a) 3 marks
3. A B C E F G H A – B – C – – E – F – G – H – Table 1 Table 1 shows the shortest distances, in miles, between eight towns, A, B, C, D, E, F, G and H. (a) Use Prim’s algorithm, starting at A, to find the minimum spanning tree for this table of distances. You must clearly state the order in which you select the edges of your tree. (3)
Nov 2021 · Paper 3D (Decision 1) · Q3(b) 1 mark
(b) State the weight of the minimum spanning tree. (1)
Nov 2021 · Paper 3D (Decision 1) · Q3(d) 2 marks
(d) Starting by deleting J, and all of its edges, find a lower bound for the length of Pranav’s route. (2)
Oct 2020 · AS Paper 2 (Decision 1) · Q3(b) 3 marks
Figure 2 represents a network of 14 roads in a town. The expression on each arc gives the time, in minutes, to travel along the corresponding road. Prim’s algorithm, starting at A, is applied to the network. The order in which the arcs are selected is AD, DH, DG, FG, EF, CG, BD. It is given that the order in which the arcs are selected is unique. (b) Using this information, find the smallest possible range of values for x, showing your working clearly. (3)
Oct 2020 · Paper 3D (Decision 1) · Q1(a) 2 marks
1. The table below shows the lengths, in km, of the roads in a network connecting seven towns, A, B, C, D, E, F and G. A B C E F G A – – – – B – – – – C – – – – – E – – – F – – – G – – – – (a) By adding the arcs from vertex D along with their weights, complete the drawing of the network on Diagram 1 in the answer book. (2)
Oct 2020 · Paper 3D (Decision 1) · Q1(b) 3 marks
(b) Use Kruskal’s algorithm to find a minimum spanning tree for the network. You should list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your minimum spanning tree. (3)
Oct 2020 · Paper 3D (Decision 1) · Q1(c) 1 mark
(c) State the weight of the minimum spanning tree. (1)

Find an Edexcel Further Maths tutor

Stuck on this? Book a trial lesson with our Further Maths tutor.

Prefer email? Send an enquiry

If you are under 18, please include a parent's contact details. Enquiries go to enquiries@alevelfurthermathstutor.com and are deleted once handled.