IB Maths AI HLGraph TheoryPaper 1 & 2Prim’s algorithm~8 min read
Minimum Spanning Trees (Prim’s Algorithm)
Prim’s algorithm finds the same minimum spanning tree as Kruskal’s but takes a different route to get there. Instead of sorting all edges first, Prim’s starts at any one vertex and grows the tree outward, always reaching to the nearest unvisited neighbour. The big bonus: it works just as cleanly on a weighted adjacency table as on a drawn graph — making it the go-to algorithm whenever the data is in matrix form.
š What you need to know
Prim’s algorithm: starts at any chosen vertex and grows the MST by repeatedly adding the cheapest edge that connects an already-selected vertex to an unselected one.
No cycle check needed: each new edge is forced to connect a new vertex, so a cycle can never form — this is why Prim’s is often considered cleaner than Kruskal’s.
Starting vertex doesn’t matter: the final MST has the same total weight no matter which vertex you start from (though the order of edges may differ).
Stops at n − 1 edges — same finish line as Kruskal’s, since the answer is the same MST.
Matrix form: Prim’s can be applied directly to a weighted adjacency table by repeatedly crossing out columns and circling smallest row entries. Kruskal’s needs the graph drawn.
Show working: examiners want the order of vertices added and the edges chosen at each step — don’t just state the final tree.
Same MST as Kruskal’s: both algorithms find an MST of the same total weight; specific edges chosen may differ when weights tie.
Growing the tree from a single vertex
Think of Prim’s algorithm as building a village outward from a single house. You pick a starting house, look at all the roads leaving it, and pave the cheapest one to its neighbour. Now you have two connected houses. Next, you look at every road leaving either of these two houses, pick the cheapest one that reaches a brand-new house, and pave it. Repeat until every house in the village is connected. That’s Prim’s algorithm.
At each step you only ever look at “boundary” edges — those with one end inside the growing tree and the other end outside. Edges between two vertices that are both already in the tree are ignored entirely; that’s how cycles are automatically avoided. After n − 1 steps every vertex is in the tree, and you’ve found the MST.
Starting at A, Prim’s adds vertices in the order A ā E ā C ā D ā B (badges 1 through 5), choosing the cheapest boundary edge at each step. The final MST has total weight 14 — the same as Kruskal’s would give on this graph.
Prim’s algorithm in symbols
start with Vtree = { vstart } ā add min-weight edge from Vtree to outside ā repeat until |Vtree| = nselects exactly n − 1 edges; total MST weight = sum of selected edges
Prim’s on a weighted adjacency table
When the graph is given as a table (a weighted adjacency matrix), drawing it out can be slow. Prim’s algorithm has a beautifully clean version that works directly on the table — the steps are: pick a starting row ā cross out its column ā circle the smallest value in that row ā cross out that column ā label the row of the newly-reached vertex ā look across all labelled rows for the next smallest. Each circled value is an edge of the MST.
Here’s the procedure laid out:
Step
Action
1
Pick a starting vertex. Label its row “1” and cross out that vertex’s column.
2
In the labelled row(s), find the smallest uncrossed entry. Circle it. This is the next MST edge.
3
Identify the column the circled value sits in — that’s the new vertex. Cross out its column and label its row with the next number.
4
Repeat steps 2ā3 until every row has been labelled. The labels give the order vertices joined the tree.
Why Prim’s beats Kruskal’s on tables: with a table, there’s no quick way to “see” cycles, so Kruskal’s cycle check becomes painful. Prim’s automatically avoids cycles (you never re-enter a vertex), so it slots into table form with no extra checks. If a question gives you a table, reach for Prim’s.
š§ Recipe — Prim’s algorithm (graph or table form)
Pick a starting vertex. Any vertex works; the final weight is the same.
From every vertex already in the tree, find the cheapest edge that leads to a vertex not in the tree.
Add that edge and its new endpoint. Record the order of selection.
Repeat step 2 until all n vertices are in the tree (i.e. you have n − 1 edges).
Sum the weights of the chosen edges — that’s the MST total weight. Draw the final tree.
Worked examples
WE 1
Prim’s algorithm on a small graph
Use Prim’s algorithm, starting at vertex A, to find the MST of the graph with vertices { A, B, C, D, E } and edges AB(6), AC(2), AD(7), BC(3), BD(5), BE(4), CD(8), CE(9), DE(1). State the order of vertices added and the total weight.
step 1: start at A; tree = { A }edges from A: AB(6), AC(2), AD(7)smallest: AC(2) ā add Cstep 2: tree = { A, C }boundary edges: AB(6), AD(7), BC(3), CD(8), CE(9)smallest: BC(3) ā add Bstep 3: tree = { A, B, C }boundary: AD(7), BD(5), BE(4), CD(8), CE(9)smallest: BE(4) ā add Estep 4: tree = { A, B, C, E }boundary: AD(7), BD(5), CD(8), DE(1)smallest: DE(1) ā add D ā done (nā1=4)total weight2 + 3 + 4 + 1 = 10order: A ā C ā B ā E ā D; weight = 10edges used: AC, BC, BE, DE ā note that DE(1) was the cheapest in the whole graph but was added last, because D wasn’t reachable from A directly cheaply.
WE 2
Same graph, different starting vertex
Apply Prim’s algorithm to the same graph in WE 1, but starting at vertex D instead. Verify that the total weight is unchanged.
step 1: start at D; tree = { D }edges from D: AD(7), BD(5), CD(8), DE(1)smallest: DE(1) ā add Estep 2: tree = { D, E }boundary: AD(7), BD(5), BE(4), CD(8), CE(9)smallest: BE(4) ā add Bstep 3: tree = { B, D, E }boundary: AB(6), AD(7), BC(3), CD(8), CE(9)smallest: BC(3) ā add Cstep 4: tree = { B, C, D, E }boundary: AB(6), AC(2), AD(7)smallest: AC(2) ā add A ā donetotal weight1 + 4 + 3 + 2 = 10order: D ā E ā B ā C ā A; weight = 10 āsame edges, same total ā the order changes but the MST itself doesn’t.
WE 3
Prim’s on a weighted adjacency table
The table below shows distances (km) between five towns. Use Prim’s algorithm starting at A to find the MST.
A
B
C
D
E
A
–
8
5
10
12
B
8
–
6
9
4
C
5
6
–
3
11
D
10
9
3
–
7
E
12
4
11
7
–
label row A ā ā ; cross out column Asmallest in row A: AC = 5 ā circlelabel row C ā ā”; cross out column Csmallest in rows A, C (uncrossed): CD = 3 ā circlelabel row D ā ā¢; cross out column Dsmallest in rows A, C, D: CB = 6 ā circlelabel row B ā ā£; cross out column Bsmallest in rows A,B,C,D: BE = 4 ā circlelabel row E ā ā¤; all rows labelled, doneedges: AC(5), CD(3), CB(6), BE(4)total = 5 + 3 + 6 + 4 = 18order: A ā C ā D ā B ā E; weight = 18 kmworking straight on the table is much faster than drawing the graph ā no need to plot anything.
WE 4
Equal weights at a step
Use Prim’s algorithm to find the MST of a graph with edges AB(5), AC(4), AD(4), BC(2), BD(6), CD(7), starting at A. If there’s a tie, either choice is acceptable.
step 1: tree = { A }edges from A: AB(5), AC(4), AD(4)tie at 4: pick AC ā add C (AD also valid)step 2: tree = { A, C }boundary: AB(5), AD(4), BC(2), CD(7)smallest: BC(2) ā add Bstep 3: tree = { A, B, C }boundary: AD(4), BD(6), CD(7)smallest: AD(4) ā add D ā donetotal weight4 + 2 + 4 = 10MST = { AC, BC, AD }; weight = 10had we picked AD instead of AC at step 1, the next steps would have given { AD, BC, AC } ā same total weight of 10.
WE 5
Practical problem ā water pipe network
A village engineer wants to connect five wells to a shared water supply by laying pipe between them (the shortest connections, in metres, are shown). Use Prim’s algorithm starting at well V to find the minimum total length of pipe needed.
V
W
X
Y
Z
V
–
20
35
40
15
W
20
–
25
30
45
X
35
25
–
10
50
Y
40
30
10
–
22
Z
15
45
50
22
–
start at V ā ā ; cross column Vsmallest in row V: VZ = 15 ā circlelabel row Z ā ā”; cross column Zsmallest in rows V, Z: VW = 20 ā circlelabel row W ā ā¢; cross column Wsmallest in rows V, W, Z: WX = 25 ā circlelabel row X ā ā£; cross column Xsmallest in rows V, W, X, Z: XY = 10 ā circlelabel row Y ā ā¤; donetotal = 15 + 20 + 25 + 10 = 70 mminimum pipe length = 70 mspot the “look out” tip: XY = 10 was the cheapest edge in the whole table, but only joined the tree at step 4 because X wasn’t reachable cheaply until step 3.
WE 6
Larger graph ā 6 vertices from a table
Apply Prim’s algorithm starting at vertex P to find the MST of the network below. State the order of vertex selection and the total weight.
P
Q
R
S
T
U
P
–
3
9
12
7
14
Q
3
–
5
10
8
11
R
9
5
–
4
6
13
S
12
10
4
–
2
15
T
7
8
6
2
–
1
U
14
11
13
15
1
–
start at P ā ā smallest in row P: PQ = 3 ā add Q ā”rows P, Q labelledsmallest uncrossed: QR = 5 ā add R ā¢rows P, Q, R labelledsmallest uncrossed: RS = 4 ā add S ā£rows P, Q, R, S labelledsmallest uncrossed: ST = 2 ā add T ā¤rows P, Q, R, S, T labelledsmallest uncrossed: TU = 1 ā add U ā„total weight3 + 5 + 4 + 2 + 1 = 15order: P ā Q ā R ā S ā T ā U; weight = 15edges: PQ, QR, RS, ST, TU ā this MST is a chain because each new vertex was always closest to the most-recently added one.
Kruskal’s vs Prim’s — which to use?
Both algorithms always find the same total MST weight; the choice depends on how the question is presented:
Situation
Use
Graph is drawn out, easy to spot edges visually
Either — Kruskal’s is often quicker for small graphs.
Data given as a weighted adjacency table
Prim’s — works directly on the table; no need to redraw.
Question specifies one method
Use that one (don’t change just to “show off”).
Large graph with many edges
Prim’s — no need to sort all edges, no cycle checks.
š” Top tips
Always label the order of vertex selection (1, 2, 3, …) — it’s a method-mark step.
Working on a table? Cross out columns and circle smallest entries clearly. Use coloured pens or labels in margins to keep tidy.
Boundary, boundary, boundary: at every step, only edges with one end inside and one end outside the current tree are candidates. Edges with both ends inside are ignored.
Cheapest edge globally may not be added first: it has to be reachable. Look how DE(1) appears late in WE 1 even though it’s the smallest weight in the graph.
If both algorithms are allowed, pick the one suited to the data: graph ā Kruskal’s, table ā Prim’s.
ā Common mistakes
Only looking at edges from the last-added vertex — Prim’s looks at edges from every vertex already in the tree, not just the most recent one.
Picking the globally smallest edge regardless of reachability — that’s Kruskal’s, not Prim’s. In Prim’s, the chosen edge must touch the existing tree.
Forgetting to cross out columns in the table version — you may revisit a vertex by accident, creating a cycle.
Not showing the selection order: just stating the final tree loses method marks.
Stopping too early or continuing past n − 1 edges: count vertices, stop when all are added.
Next up — The Chinese Postman Problem. Once you can find a minimum spanning tree, the next class of network problems asks: can a postman walk along every road exactly once and return home? This is where Eulerian trails and circuits come in, and you’ll use the degrees of vertices (back from the Introduction page) to decide whether such a route exists.
Need help with Graph Theory?
Get 1-on-1 help from an IB examiner who knows exactly what Paper 1 & 2 are looking for.
