Mathematics Standard • Year 12 • Module 5 • Lesson 8
Prim's Algorithm — Problem Set
Apply Prim's to planning problems where one vertex is the natural starting point — depots, exchanges, treatment plants — and compare with Kruskal's where useful.
Problem 1 — Sydney delivery depot
A logistics company has a central depot D and four warehouses A, B, C, E. Road-link costs in $thousands per route: DA = 7, DB = 5, DC = 8, DE = 6, AB = 9, AC = 11, BC = 4, BE = 10, CE = 3.
Set up: What are we solving for?
(i) Apply Prim's starting at the depot D. Show the tree, candidates, and chosen edge at each step. 3 marks
(ii) State the MST edges and the total cost. 1 mark
(iii) Comparing with Kruskal's on the same network, would you expect the same total cost? Briefly justify. 1 mark
Stuck? Revisit lesson § Card 02 — Kruskal's vs Prim's.Problem 2 — Country telephone exchange
A Telstra exchange E is to be connected by underground cable to four nearby substations P, Q, R, S. Costs in $thousands per cable: EP = 9, EQ = 12, ER = 7, ES = 15, PQ = 5, PR = 8, PS = 14, QR = 6, QS = 10, RS = 4.
Set up: What are we solving for?
(i) Apply Prim's starting at the exchange E. Show your candidate edges at each step. 3 marks
(ii) State the MST edges and the total minimum cost. 1 mark
(iii) Re-apply Prim's, this time starting at substation S. Confirm the total cost is the same. 2 marks
Stuck? Different starting vertices can give different orderings — but the MST total is a property of the network.Problem 3 — Wollongong water treatment
A water utility plans to connect a central treatment plant T to six suburbs. Pipeline costs in $thousands per pipe (from the proposed network):
TA = 14, TB = 12, TC = 18, TD = 11, AB = 8, AC = 13, BC = 6, BD = 7, CD = 9, BE = 15, CF = 10, DE = 5, DF = 16, EF = 4.
Set up: What are we solving for?
(i) Apply Prim's starting at the plant T. Record tree, candidates and chosen edge at each step. 3 marks
(ii) List the MST edges and the total cost. 1 mark
(iii) The CEO insists the cheapest single edge of $4k (EF) must be in any MST. State whether this is true here, and explain in one sentence. 1 mark
Stuck? The globally cheapest edge in a network is always in an MST (provided it has a unique cheapest weight or appears in some MST).Problem 4 — Does the starting vertex matter?
A school IT team is connecting six campus buildings with fibre. Costs in metres of cable: AB = 25, AC = 18, AD = 30, BC = 12, BD = 20, BE = 22, CD = 10, CE = 15, CF = 28, DE = 8, DF = 14, EF = 9.
Set up: What are we solving for?
(i) Apply Prim's starting at A. List the MST edges in the order they are added, then the total. 3 marks
(ii) Apply Prim's starting at F. List the MST edges in the order they are added, then the total. 2 marks
(iii) Compare your answers to (i) and (ii). What changes and what stays the same? 1 mark
Stuck? The order in which edges are added almost always changes; the final set of edges may be identical or differ only when weights are tied.Problem 5 — Choose the algorithm
You are given a 10-vertex network presented as an adjacency table (so you read the edges directly off a diagram). Your friend has the same network as an unsorted list of 45 edges with weights.
Set up: Which algorithm should each of you use, and why?
(i) State which algorithm is most efficient for the diagram version and explain in one sentence. 2 marks
(ii) State which algorithm is most efficient for the unsorted-list version and explain in one sentence. 2 marks
(iii) If both of you produce a valid MST, what must be true about your two answers, regardless of method? 1 mark
Stuck? Revisit lesson § Card 02 — comparison table.How did this worksheet feel?
What I'll revisit before next class:
Problem 1 — Sydney delivery depot
Set up. Apply Prim's starting at D to find the cheapest set of road links connecting D to all four warehouses.
(i) {D}: DA(7), DB(5), DC(8), DE(6). Add DB(5). {B,D}: DA(7), DC(8), DE(6), BA(9), BC(4), BE(10). Add BC(4). {B,C,D}: DA(7), DE(6), BA(9), BE(10), CA(11), CE(3). Add CE(3). {B,C,D,E}: DA(7), BA(9), CA(11), BE(10 cycle). Add DA(7). Done.
(ii) MST edges: DB, BC, CE, DA. Total = 5 + 4 + 3 + 7 = $19 thousand.
(iii) Yes — both algorithms find a minimum spanning tree, which always has the same total weight for a given network.
Problem 2 — Country exchange
Set up. Apply Prim's starting at the exchange to find the cheapest cable layout linking E to all four substations.
(i) {E}: EP(9), EQ(12), ER(7), ES(15). Add ER(7). {E,R}: EP(9), EQ(12), ES(15), RP(8), RQ(6), RS(4). Add RS(4). {E,R,S}: EP(9), EQ(12), RP(8), RQ(6), PS(14), QS(10). Add RQ(6). {E,Q,R,S}: EP(9), RP(8), PS(14), PQ(5). Add PQ(5). Done.
(ii) MST: ER, RS, RQ, PQ. Total = 7 + 4 + 6 + 5 = $22 thousand.
(iii) From S: {S}: ES(15), PS(14), QS(10), RS(4). Add RS(4). {R,S}: ES(15), PS(14), QS(10), ER(7), PR(8), QR(6). Add ER(7). {E,R,S}: PS(14), QS(10), PR(8), QR(6), EP(9), EQ(12). Add QR(6). {E,Q,R,S}: PS(14), PR(8), EP(9), PQ(5). Add PQ(5). Done. Total = 4 + 7 + 6 + 5 = $22 thousand ✓ same as in (ii).
Problem 3 — Wollongong water treatment
Set up. Apply Prim's starting at the plant T to find the cheapest pipeline layout.
(i) Vertices: T, A, B, C, D, E, F (7 vertices ⇒ 6 MST edges). {T}: TA(14), TB(12), TC(18), TD(11). Add TD(11). {D,T}: TA(14), TB(12), TC(18), AB?(not given via D), BD(7), CD(9), DE(5), DF(16). Add DE(5). {D,E,T}: TA(14), TB(12), TC(18), BD(7), CD(9), EF(4), BE(15), DF(16). Add EF(4). {D,E,F,T}: TA(14), TB(12), TC(18), BD(7), CD(9), CF(10), DF(16 cycle), BE(15). Add BD(7). {B,D,E,F,T}: TA(14), TC(18), CD(9), CF(10), AB(8), AC(13), BC(6). Add BC(6). {B,C,D,E,F,T}: TA(14), AB(8), AC(13), CF(10 cycle), CD(9 cycle). Add AB(8). Done.
(ii) MST: TD, DE, EF, BD, BC, AB. Total = 11 + 5 + 4 + 7 + 6 + 8 = $41 thousand.
(iii) True for this network — EF(4) is the globally cheapest edge and (because its weight is strictly less than every other) it must appear in every MST.
Problem 4 — Campus fibre
Set up. Apply Prim's from two different starting vertices and compare.
(i) From A: {A}: AB(25), AC(18), AD(30). Add AC(18). {A,C}: AB(25), AD(30), BC(12), CD(10), CE(15), CF(28). Add CD(10). {A,C,D}: AB(25), AD(30 cycle), BC(12), CE(15), CF(28), BD(20), DE(8), DF(14). Add DE(8). {A,C,D,E}: BC(12), CE(15 cycle), CF(28), BD(20), DF(14), BE(22), EF(9). Add EF(9). {A,C,D,E,F}: BC(12), BD(20), BE(22), DF(14 cycle), CF(28 cycle). Add BC(12). Done. MST (in order): AC, CD, DE, EF, BC. Total = 18 + 10 + 8 + 9 + 12 = 57 m.
(ii) From F: {F}: CF(28), DF(14), EF(9). Add EF(9). {E,F}: CF(28), DF(14), DE(8), CE(15), BE(22). Add DE(8). {D,E,F}: CF(28), DF(14 cycle), CE(15), BE(22), AD(30), BD(20), CD(10). Add CD(10). {C,D,E,F}: CF(28 cycle), CE(15 cycle), BE(22), AD(30), BD(20), AC(18), BC(12). Add BC(12). {B,C,D,E,F}: BE(22 cycle), AD(30), BD(20 cycle), AC(18), AB(25). Add AC(18). Done. MST (in order): EF, DE, CD, BC, AC. Total = 9 + 8 + 10 + 12 + 18 = 57 m.
(iii) What changed: the order in which edges were added. What stayed the same: the set of MST edges and the total weight (57 m).
Problem 5 — Choose the algorithm
Set up. Match the algorithm to the situation that minimises effort.
(i) Prim's — from a diagram you can scan the edges touching the growing tree by eye, which is much faster than sorting all 45 edges first.
(ii) Kruskal's — sorting an unsorted list is exactly what Kruskal's needs, and once sorted you simply walk down the list adding edges.
(iii) Both MSTs must have the same total weight (although the specific edges may differ where weights are tied).