Mathematics Standard • Year 12 • Module 5 • Lesson 8
Prim's Algorithm — Skill Drill
Build fluency in Prim's: pick a starting vertex, list the candidate edges that reach the outside, add the cheapest, repeat until every vertex is in the tree.
1. Quick recall
Answer each question in the space provided. 1 mark each
Q1.1 Complete the description: Prim's algorithm starts at ____________________, and at each step adds the cheapest edge that joins a vertex ____________________ the tree to a vertex ____________________ the tree.
Q1.2 Why can Prim's never create a cycle? Answer in one sentence.
Q1.3 A network has 10 vertices. How many edges does Prim's add? ____
2. Worked example — Prim's from vertex A
Follow every line. Each step has a reason on the right.
Problem. A network on A, B, C, D, E has edges AB = 5, AC = 8, BC = 6, BD = 4, CD = 7, CE = 9, DE = 3. Apply Prim's starting at A.
Step 1 — Tree = {A}. Candidate edges from A:
AB(5), AC(8) → cheapest = AB(5). Add. Tree = {A, B}.
Reason: edges from the tree to outside; AB is the cheapest.
Step 2 — Tree = {A, B}. Candidate edges from {A,B} to outside:
AC(8), BC(6), BD(4) → cheapest = BD(4). Add. Tree = {A, B, D}.
Step 3 — Tree = {A, B, D}. Candidates:
AC(8), BC(6), CD(7), DE(3) → cheapest = DE(3). Add. Tree = {A, B, D, E}.
Step 4 — Tree = {A, B, D, E}. Candidates:
AC(8), BC(6), CD(7), CE(9) → cheapest = BC(6). Add. Tree = {A, B, C, D, E}.
Reason: every vertex now in the tree. Stop.
Conclusion. MST edges: AB, BD, DE, BC. Total = 5 + 4 + 3 + 6 = 18. (Same total as Kruskal's — different order, same answer.)
3. Faded example — fill in the missing steps
Network on P, Q, R, S, T with PQ = 7, PR = 3, PS = 8, QR = 5, QS = 2, RS = 4, RT = 9, ST = 6. Apply Prim's starting at P. 4 marks
Step 1 — Tree = {P}. Candidates: PQ(__), PR(__), PS(__). Cheapest = ____. Add. Tree = {____}.
Step 2 — Tree = {P, R}. Candidates: PQ(__), QR(__), RS(__), PS(__), RT(__). Cheapest = ____. Add. Tree = {____}.
Step 3 — Tree = {____}. Candidates: ____, ____, ____, ____. Cheapest = ____. Add. Tree = {____}.
Step 4 — Tree = {____}. Candidates: ____, ____. Cheapest = ____. Add. Tree = {P, Q, R, S, T}. Stop.
Conclusion. MST edges: ____. Total = ____ + ____ + ____ + ____ = ____.
4. Graduated practice — apply Prim's
Show your tree after each step.
Foundation — single-step facts (4 questions)
| Q | Problem | Answer |
|---|---|---|
| 4.1 1 | Prim's on a network with 15 vertices adds how many edges? | |
| 4.2 1 | True / False: Prim's must check whether a candidate edge forms a cycle. | |
| 4.3 1 | True / False: Prim's and Kruskal's always give the same total MST weight (for a given connected weighted network). | |
| 4.4 1 | You are at tree = {A, C}. Candidates with weights AB(6), CB(3), CD(4), CE(7). Which edge is added next? |
Standard — typical HSC difficulty (6 questions)
Always list the candidate edges then circle the cheapest.
4.5 Apply Prim's starting at A: AB = 4, AC = 2, BC = 5, BD = 1, CD = 3, CE = 6, DE = 2. List MST edges and total. 2 marks
4.6 Apply Prim's to the same network in 4.5 starting at D. Do you get the same set of MST edges as in 4.5? 2 marks
4.7 Apply Prim's starting at B on a network with AB = 3, AC = 7, AD = 5, BC = 2, BD = 6, CD = 4. 2 marks
4.8 Apply Prim's starting at A: AB = 1, BC = 4, CD = 2, DE = 5, EA = 3, AC = 6, CE = 7. List MST edges and total. 2 marks
4.9 A student claims the candidates at step 3 of Prim's must include every edge between every pair of vertices in the tree. Is this correct? Explain in one sentence. 2 marks
4.10 Apply Prim's starting at C: AB = 4, AC = 5, AD = 8, BC = 2, BD = 6, BE = 7, CD = 3, CE = 9, DE = 1. State MST edges and total. 2 marks
Extension — combine ideas (2 questions)
4.11 A network has 6 vertices. (a) When Prim's starts at any vertex, must the MST contain the cheapest single edge in the whole network? Justify your answer in one sentence. (b) Why does the starting vertex never change the final MST weight? 3 marks
4.12 Apply Prim's starting at A to a 6-vertex network with AB = 10, AC = 6, AD = 12, BC = 5, BE = 3, CD = 4, CE = 9, CF = 7, DE = 11, DF = 2, EF = 8. State the MST edges, total weight, and the order in which Prim's added each edge. 3 marks
5. Self-check the easy 3
Tick the first three once you've checked your method works.
How did this worksheet feel?
What I'll revisit before next class:
Q1.1 — Prim's description
Starts at any one (chosen) vertex, and at each step adds the cheapest edge joining a vertex inside the tree to a vertex outside the tree.
Q1.2 — Why no cycle
Every edge Prim's adds connects an outside vertex (not yet in the tree) to an inside vertex, so the new vertex cannot already have a path back into the tree — no cycle is possible.
Q1.3 — Edges added on 10 vertices
n − 1 = 9 edges.
Q3 — Faded example (PQRST with 8 edges)
Step 1: Tree {P}. Candidates PQ(7), PR(3), PS(8). Cheapest PR(3). Tree {P, R}.
Step 2: Candidates PQ(7), QR(5), RS(4), PS(8), RT(9). Cheapest RS(4). Tree {P, R, S}.
Step 3: Tree {P, R, S}. Candidates PQ(7), QR(5), QS(2), ST(6), RT(9). Cheapest QS(2). Tree {P, Q, R, S}.
Step 4: Tree {P, Q, R, S}. Candidates ST(6), RT(9). Cheapest ST(6). Tree {P, Q, R, S, T}.
MST: PR, RS, QS, ST. Total = 3 + 4 + 2 + 6 = 15.
Q4.1 — Edges on 15 vertices
n − 1 = 14 edges.
Q4.2 — Cycle check?
False — Prim's adds only edges to outside vertices, so cycles cannot form.
Q4.3 — Same total weight?
True — both algorithms find a minimum spanning tree, which always has the same total weight (although the specific edges chosen can differ if there are ties).
Q4.4 — Next edge from tree {A, C}
Candidates: AB(6), CB(3), CD(4), CE(7). Smallest = CB(3).
Q4.5 — Prim's from A on 7-edge network
Tree {A}: AB(4), AC(2). Add AC(2). {A,C}: AB(4), CB(5), CD(3), CE(6). Add CD(3). {A,C,D}: AB(4), CB(5), CE(6), DB(1), DE(2). Add DB(1). {A,B,C,D}: CE(6), DE(2), CB(5 cycle). Add DE(2). Done. MST: AC, CD, DB, DE. Total = 2 + 3 + 1 + 2 = 8.
Q4.6 — Prim's from D on same network
Tree {D}: DB(1), DC(3), DE(2). Add DB(1). {B,D}: DC(3), DE(2), BA(4), BC(5). Add DE(2). {B,D,E}: DC(3), BA(4), BC(5), EC(6). Add DC(3). {B,C,D,E}: BA(4), CA(2). Add CA(2). Done. MST: DB, DE, DC, CA. Total = 1 + 2 + 3 + 2 = 8. Same edges as in 4.5 (just added in a different order).
Q4.7 — Prim's from B
{B}: AB(3), BC(2), BD(6). Add BC(2). {B,C}: AB(3), BD(6), AC(7), CD(4). Add AB(3). {A,B,C}: BD(6), CD(4), AD(5). Add CD(4). Done. MST: BC, AB, CD. Total = 2 + 3 + 4 = 9.
Q4.8 — Prim's from A on 5-cycle plus chords
{A}: AB(1), EA(3), AC(6). Add AB(1). {A,B}: EA(3), AC(6), BC(4). Add EA(3). {A,B,E}: AC(6), BC(4), CE(7). Add BC(4). {A,B,C,E}: AC(6 cycle), CE(7 cycle), CD(2). Add CD(2). Done. MST: AB, EA, BC, CD. Total = 1 + 3 + 4 + 2 = 10.
Q4.9 — Are all in-tree edges candidates?
No — candidates are only edges with one endpoint in the tree and one outside; edges with both endpoints in the tree are ignored (they would form cycles anyway).
Q4.10 — Prim's from C
{C}: AC(5), BC(2), CD(3), CE(9). Add BC(2). {B,C}: AC(5), CD(3), CE(9), AB(4), BD(6), BE(7). Add CD(3). {B,C,D}: AC(5), CE(9), AB(4), BE(7), DE(1), AD(8). Add DE(1). {B,C,D,E}: AC(5), AB(4), BE(7 cycle), AD(8), CE(9 cycle). Add AB(4). Done. MST: BC, CD, DE, AB. Total = 2 + 3 + 1 + 4 = 10.
Q4.11 — Cheapest single edge and starting vertex
(a) Yes — the unique cheapest edge must be in every MST (if you removed it, you would not have an MST), and Prim's will always pick it up when its endpoints become reachable. (Slight caveat if there is a tie for cheapest.)
(b) Different starting vertices may produce different orderings or even different edges (when there are ties), but the total minimum weight of an MST is a property of the network, not of the algorithm or starting vertex.
Q4.12 — Prim's from A on 6-vertex network
{A}: AB(10), AC(6), AD(12). Add AC(6). {A,C}: AB(10), AD(12), BC(5), CD(4), CE(9), CF(7). Add CD(4). {A,C,D}: AB(10), BC(5), CE(9), CF(7), DE(11), DF(2). Add DF(2). {A,C,D,F}: AB(10), BC(5), CE(9), DE(11), EF(8). Add BC(5). {A,B,C,D,F}: AD(12 cycle), BE(3), CE(9 cycle), DE(11), EF(8). Add BE(3). Done.
MST edges (in added order): AC, CD, DF, BC, BE. Total = 6 + 4 + 2 + 5 + 3 = 20.