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.
June 2025 · AS Paper 2 (Decision 1) · Q1(b)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This was a very accessible opener, with a significant number of learners scoring full marks, however a surprising number of learners did not score highly being full marks despite it being a very accessible question. Part a) was generally answered very well with a majority of learners scoring at least two out of the three available marks, and most securing full marks. Very few descending sorts or quick sorts were seen, and most were able to show just the final results of each pass rather than every comparison. A small group of learners chose to write out every swap, and not just the result at the end of the pass, which was very time consuming for them on an already tightly timed paper. It was most common to just stop after the 5th pass, with no 6th pass or “sort complete” statement made. Some learners used a more unusual “cross arrow” notation, where learners were trying to show all the swaps that took place in a single line – this was confusing to follow and more often than not led to a mistake in one of the passes. Part b) saw a number of learners use Kruskal’s or a version of the nearest neighbour algorithm, or considering and rejecting arcs in a hybrid version of Prim’s and Kruskal’s. Several learners chose to draw the distance matrix in order to perform Prim’s, which was an unnecessary use of their time. The third arc dictated whether a candidate had correctly used Prim’s, and therefore if the wrong algorithm was used, the candidate lost both the method and the accuracy mark. Nonetheless a majority scored all marks here. Part c) provided easy marks for those who had correctly used Prim’s in part b), but also the opportunity for full marks even if Kruskal’s had been used in part b). There were a few errors in adding up the arc lengths, with a variety of total lengths in the range 85-89. Almost all learners who had a correct MST in b) also scored the two marks in c), and thus a large majority scored both of these marks).
Key points from the mark scheme and examiner's report
Prim from A: AC, BC, CF, EF, DF
the third arc shows whether Prim (not Kruskal) was used
any rejection implies M0
listing nodes ACBFED scores M1 only
June 2025 · AS Paper 2 (Decision 1) · Q1(c)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This was a very accessible opener, with a significant number of learners scoring full marks, however a surprising number of learners did not score highly being full marks despite it being a very accessible question. Part a) was generally answered very well with a majority of learners scoring at least two out of the three available marks, and most securing full marks. Very few descending sorts or quick sorts were seen, and most were able to show just the final results of each pass rather than every comparison. A small group of learners chose to write out every swap, and not just the result at the end of the pass, which was very time consuming for them on an already tightly timed paper. It was most common to just stop after the 5th pass, with no 6th pass or “sort complete” statement made. Some learners used a more unusual “cross arrow” notation, where learners were trying to show all the swaps that took place in a single line – this was confusing to follow and more often than not led to a mistake in one of the passes. Part b) saw a number of learners use Kruskal’s or a version of the nearest neighbour algorithm, or considering and rejecting arcs in a hybrid version of Prim’s and Kruskal’s. Several learners chose to draw the distance matrix in order to perform Prim’s, which was an unnecessary use of their time. The third arc dictated whether a candidate had correctly used Prim’s, and therefore if the wrong algorithm was used, the candidate lost both the method and the accuracy mark. Nonetheless a majority scored all marks here. Part c) provided easy marks for those who had correctly used Prim’s in part b), but also the opportunity for full marks even if Kruskal’s had been used in part b). There were a few errors in adding up the arc lengths, with a variety of total lengths in the range 85-89. Almost all learners who had a correct MST in b) also scored the two marks in c), and thus a large majority scored both of these marks).
Key points from the mark scheme and examiner's report
draw the tree AC, BC, CF, EF, DF
weight 83
adding slips gave 85 to 89
June 2024 · Paper 3D (Decision 1) · Q2(a)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Parts (a), (b) and (c) were generally well approached and it was clear that many candidates understood how to apply Prim’s algorithm. There were a small number of responses which chose to start the Prim's at a node other than D, but they were rare. Some candidates lost marks for not listing the arcs of the tree explicitly, sometimes giving a list of nodes instead, or even simply numbering the top of the matrix with the order of selection followed by giving the weight of the tree only. There were occasional errors in the order of selection, for example sometimes EH and EJ were incorrectly interchanged, and other errors arose from the apparent application of a nearest neighbour approach resulting in a route rather than a tree. In (b), most who used their minimum spanning tree from part (a) generally made fewer errors than those who recreated the work to produce an MST here. Nonetheless, most did arrive at the correct lower bound of 281. In the comparison of upper and lower bounds in parts (f) and (h), it was clear that most
Key points from the mark scheme and examiner's report
Prim from D on the matrix: DE, AD, EH, EJ, CD, BC, GH, CF
list arcs in order, not just nodes or numbers
EH/EJ order swapped by some
June 2024 · Paper 3D (Decision 1) · Q2(b)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Parts (a), (b) and (c) were generally well approached and it was clear that many candidates understood how to apply Prim’s algorithm. There were a small number of responses which chose to start the Prim's at a node other than D, but they were rare. Some candidates lost marks for not listing the arcs of the tree explicitly, sometimes giving a list of nodes instead, or even simply numbering the top of the matrix with the order of selection followed by giving the weight of the tree only. There were occasional errors in the order of selection, for example sometimes EH and EJ were incorrectly interchanged, and other errors arose from the apparent application of a nearest neighbour approach resulting in a route rather than a tree. In (b), most candidates were able to write down the weight of the MST correctly, even some who had made errors in Prims and the vast majority were able to draw the tree correctly in part (c).
Key points from the mark scheme and examiner's report
241 miles
June 2024 · Paper 3D (Decision 1) · Q2(c)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Parts (a), (b) and (c) were generally well approached and it was clear that many candidates understood how to apply Prim’s algorithm. There were a small number of responses which chose to start the Prim's at a node other than D, but they were rare. Some candidates lost marks for not listing the arcs of the tree explicitly, sometimes giving a list of nodes instead, or even simply numbering the top of the matrix with the order of selection followed by giving the weight of the tree only. There were occasional errors in the order of selection, for example sometimes EH and EJ were incorrectly interchanged, and other errors arose from the apparent application of a nearest neighbour approach resulting in a route rather than a tree. In (b), most errors in Prims and the vast majority were able to draw the tree correctly in part (c).
Key points from the mark scheme and examiner's report
draw the tree DE, AD, EH, EJ, CD, BC, GH, CF on Diagram 1
June 2024 · Paper 3D (Decision 1) · Q2(d)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
In part (d) the majority of candidate realised they needed to double the weight of their minimum spanning tree to obtain the upper bound although some candidates were confused here with the method for the calculation of the lower bound and instead added ‘two shortest lengths’ or sometimes added just AD.
Key points from the mark scheme and examiner's report
initial upper bound is twice the MST: 482
some added the two shortest arcs (lower-bound method)
June 2024 · Paper 3D (Decision 1) · Q2(g)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
In part (g), many candidates started again, rather than adapting the work already done. Those who used their minimum spanning tree from part (a) generally made fewer errors than those
Key points from the mark scheme and examiner's report
adapt the MST: RMST = 241 − 26 = 215, plus AD 26 and AF 40 = 281
reusing the MST avoided errors
June 2023 · AS Paper 2 (Decision 1) · Q3(c)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
vertex, which scored no marks. In part (c) many candidates did apply Prim’s algorithm correctly (from C) but it was common to see candidates scoring only one mark in this part for explicitly rejecting arcs (by design Prim’s algorithm grows in a connected fashion by only considering nodes that are not already part of the MST and therefore cycles are never formed (and therefore there is no need to ‘reject’ arcs)). Those candidates who had found the correct MST usually went on to score the mark in part (d) for stating its total length.
Key points from the mark scheme and examiner's report
from C: CD, BD, DG, EG, GH, EF, FJ, AB
Prim never needs rejections, explicit rejections cap the score at M1
June 2023 · AS Paper 2 (Decision 1) · Q3(d)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
went on to score the mark in part (d) for stating its total length.
Key points from the mark scheme and examiner's report
155 km
June 2023 · Paper 3D (Decision 1) · Q5(b)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Part (b) was generally well answered, with a good number scoring full marks. Many candidates were able to accurately apply Prim’s algorithm, but some candidates worked solely on the table, and did not follow the instruction to state the order in which arcs were selected which lost them the final accuracy mark. A minority of candidates used a version of the Nearest Neighbour Algorithm to generate a spanning tree. Several candidates found the weight of their MST which was not required for part (b), although it could be used when finding the RMST later.
Key points from the mark scheme and examiner's report
Prim from A on the table: AG, AF, DF, AB, BC, CJ, HJ, EJ
state the arcs in order, not just numbers on the table
June 2023 · Paper 3D (Decision 1) · Q5(d)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Part (d) proved more challenging and was not attempted by a significant number of candidates. Very few candidates recognised how they could adapt their MST from (b) to answer (d) efficiently and instead found the RMST again (and this was often done incorrectly). This was one of the parts of the paper most likely to be left unanswered by candidates with a significant number moving on once part (c) was completed. Those candidates who found the correct RMST tended to score both marks.
Key points from the mark scheme and examiner's report
residual MST = 141 − 8 = 133 (reuse the MST from (b) without AG) + two smallest arcs at G (8 + 23) = 164
often not attempted
June 2022 · AS Paper 2 (Decision 1) · Q1(b)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Examiners commented on the fact that many fully complete and correct responses were seen to the sort to be completed in ascending order). In (b) (applying Kruskal’s algorithm) full marks was the modal score, though occasionally incorrect arcs were seen (or correct arcs seen but stated in the wrong order). A small minority failed to mention/show any rejections, therefore scoring no marks, as this is the key process when applying Kruskal’s algorithm. Some candidates wasted time writing our “reject, forms a cycle” several times, which is better abbreviated as simply ‘reject’. Occasionally Prim’s algorithm was used. In (c) those who had
Key points from the mark scheme and examiner's report
DE, CF, CD, reject CE, BC, EG, reject FG, reject BD, AB
rejections must be shown (none shown scores 0)
arcs not weights
Prim's occasionally used
June 2022 · AS Paper 2 (Decision 1) · Q1(c)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Examiners commented on the fact that many fully complete and correct responses were seen to abbreviated as simply ‘reject’. Occasionally Prim’s algorithm was used. In (c) those who had answered (b) correctly almost always scored both marks for the correct diagram and the correct total weight of the minimum spanning tree.
Key points from the mark scheme and examiner's report
tree AB, BC, CF, CD, DE, EG
total weight 230
Nov 2021 · Paper 3D (Decision 1) · Q3(a)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This was the best answered question on the paper covering the topic of minimum connectors and the travelling salesperson problem. Most candidates correctly saw the link between finding the MST and its weight in parts (a) and (b), and the link to the lower bound in (d).
Key points from the mark scheme and examiner's report
Prim on the matrix from A: AH, AB, DH, CD, CE, DG, EF
arcs in order, no rejections (Kruskal-style rejections cap at M1)
Nov 2021 · Paper 3D (Decision 1) · Q3(b)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This was the best answered question on the paper covering the topic of minimum connectors and the travelling salesperson problem. Most candidates correctly saw the link between finding the MST and its weight in parts (a) and (b), and the link to the lower bound in (d).
Key points from the mark scheme and examiner's report
183 miles
Nov 2021 · Paper 3D (Decision 1) · Q3(d)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This was the best answered question on the paper covering the topic of minimum connectors and the travelling salesperson problem. Most candidates correctly saw the link between finding the MST and its weight in parts (a) and (b), and the link to the lower bound in (d).
Key points from the mark scheme and examiner's report
residual MST 183 + two smallest arcs at J (25 + 27) = 235 miles
Oct 2020 · AS Paper 2 (Decision 1) · Q3(b)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
In part (b) candidates had to use the information about the order in which the arcs were added to the minimum spanning tree using Prim’s algorithm to find the smallest possible range of values for x. Therefore, because arc AD, not AB, was added to the tree first this implies that the weight of arc AB must be greater than the weight of arc AD and hence 2 10 3 2 12. x x x + > - ⇒ < Furthermore as the final arc added to the tree was BD this implies that's the weight of BD must be less than the weight of all the other arcs incident to B and hence 2 10 20 5. x x + > ⇒ > The final part of this question required candidates to use an appropriate algorithm, in this case
Key points from the mark scheme and examiner's report
AD chosen before AB so 2x + 10 > 3x − 2, x < 12
BD (20) chosen last for B so 2x + 10 > 20, x > 5
5 < x < 12
Oct 2020 · Paper 3D (Decision 1) · Q1(a)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Almost all candidates scored both marks in (a), with just a few omitting one of the arcs. Although the majority correctly applied Kruskal’s algorithm to find the MST, a surprising number of candidates lost two of the three marks here, due to including extra arcs such as BD or AE. As ever, a few listed only those arcs selected, without any reference to rejections, consequently losing all three marks for failing to demonstrate their use of the algorithm. Also a few candidates lost the marks for using Prim instead. Presentation of the answer can create difficulties both for candidates and examiners. Listing the arcs vertically down the page, in ascending order, with ticks or crosses to indicate selections and rejections, generally proves the best way for candidates. Those that insist on writing “reject, forms a cycle” many times are simply wasting time. Part (c)
Key points from the mark scheme and examiner's report
add DA 22, DB 27, DC 33, DF 42 to Diagram 1
one arc was occasionally omitted
Oct 2020 · Paper 3D (Decision 1) · Q1(b)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Almost all candidates scored both marks in (a), with just a few omitting one of the arcs. Although the majority correctly applied Kruskal’s algorithm to find the MST, a surprising number of candidates lost two of the three marks here, due to including extra arcs such as BD or AE. As ever, a few listed only those arcs selected, without any reference to rejections, consequently losing all three marks for failing to demonstrate their use of the algorithm. Also a few candidates lost the marks for using Prim instead. Presentation of the answer can create difficulties both for candidates and examiners. Listing the arcs vertically down the page, in ascending order, with ticks or crosses to indicate selections and rejections, generally proves the best way for candidates. Those that insist on writing “reject, forms a cycle” many times are simply wasting time. Part (c) was almost always correct if following the correct MST.
Key points from the mark scheme and examiner's report