Your weak spots

Insights load after your first practice round.

Module 6 · L5 of 12 ~30 min MS12-7 ⚡ +50 XP available

Minimum Spanning Trees

Australian Gas Networks uses minimum spanning tree algorithms to plan new pipeline routes — minimising total pipe length directly reduces infrastructure spend. Two algorithms (Kruskal's and Prim's) always find the cheapest way to connect all nodes, even in networks with hundreds of edges.

Today's hook — A council needs to connect 5 parks with walking paths. Edge weights represent costs ($000s). How would you minimise total cost while connecting all parks?

0/5QUESTS

Worksheets

Practise this lesson

Three printable worksheets that build from foundations to mastery — or build your own from any module’s questions.

Build Foundations & guided practice Apply Application practice Master Mastery challenge Build custom Build your own from any module question

Recall — your gut answer first

+5 XP warm-up

A council needs to connect 5 parks with walking paths. The possible paths and their costs ($000s) are: A–B: 4, A–C: 2, B–C: 3, B–D: 6, C–D: 1, C–E: 5, D–E: 2. How would you minimise total cost?

Before reading on — write your strategy.

auto-saved

The big idea — two algorithms, same answer

reference

A minimum spanning tree (MST) connects all vertices with minimum total edge weight. Both Kruskal's and Prim's algorithms always find the MST — they just build it differently.

Kruskal's algorithm: sort all edges by weight; add the cheapest edge that doesn't form a cycle; repeat until n−1 edges added.

Prim's algorithm: start at any vertex; always add the cheapest edge connecting the current tree to a new vertex; repeat until all vertices included.

Same total weight: both algorithms produce an MST with the same total weight (though possibly different structure if weights are equal).

Weighted network: a network where each edge has a numerical weight (cost, distance, time, etc.).

For the parks problem: MST edges C–D(1), A–C(2), D–E(2), B–C(3). Total = 8 ($8,000). Four edges for 5 vertices (n−1=4). ✓

Kruskal's = global sort

Sort ALL edges from cheapest to most expensive. Add each to the tree unless it creates a cycle. Best when edge list is given.

Prim's = local grow

Start anywhere. Each step, add the cheapest edge connecting the current tree to any new vertex. Best when working from a diagram.

Always n−1 edges

Any MST of an n-vertex network has exactly n−1 edges. Stop both algorithms when you reach n−1 edges.

What you will master

Know

Key facts

MST connects all vertices with minimum weight
Kruskal's: sort edges, add cheapest non-cycle
Prim's: grow tree from one vertex

Understand

Concepts

Why both algorithms give same total weight
When to use each algorithm
Role of cycle detection in Kruskal's

Can do

Skills

Apply Kruskal's to a weighted network
Apply Prim's from a specified start vertex
Calculate minimum total weight

Key terms

Weighted networkA network where each edge has a numerical weight representing cost, distance or time.

Minimum spanning tree (MST)A spanning tree of a weighted network with the smallest possible total edge weight.

Kruskal's algorithmMST algorithm: sort all edges by weight; add cheapest that doesn't form a cycle; repeat.

Prim's algorithmMST algorithm: start at any vertex; grow tree by always adding the cheapest adjacent edge to a new vertex.

Total weightThe sum of all edge weights in the minimum spanning tree — the minimum total cost.

Cycle detectionIn Kruskal's: before adding an edge, check if it connects two vertices already in the same tree component.

Kruskal's algorithm — start with the cheapest edges

core concept

Kruskal's algorithm steps:

List all edges sorted from cheapest to most expensive.
Add the cheapest edge to the tree.
For each subsequent edge: if adding it does NOT create a cycle → add it. If it creates a cycle → skip it.
Stop when you have $n-1$ edges.

How to check for a cycle: an edge creates a cycle if both its endpoints are already in the current tree and are already connected to each other (in the same component).

Example: 5 vertices, edges sorted: C–D(1), A–C(2), D–E(2), B–C(3), A–B(4), B–D(6), C–E(5).
Add C–D(1) ✓. Add A–C(2) ✓. Add D–E(2) ✓. Add B–C(3) ✓ — now 4 edges, all 5 vertices connected. Stop.
Total weight = 1+2+2+3 = 8.

What to write in your book

Kruskal's: sort edges → add cheapest → skip if cycle → stop at n−1 edges.
Cycle check: are both endpoints already connected in the current tree?

Quick check: In Kruskal's algorithm, when do you skip an edge?

Prim's algorithm — grow the tree from one vertex

core concept

Prim's algorithm steps:

Choose any starting vertex. It is now in the tree.
Look at all edges connecting the current tree to vertices NOT yet in the tree.
Add the cheapest such edge (and its new vertex) to the tree.
Repeat steps 2–3 until all vertices are in the tree.

Key difference from Kruskal's: Prim's grows from a single starting point. Kruskal's picks edges globally regardless of location.

Same example with Prim's starting at A:
From A: cheapest edge to new vertex = A–C(2). Add C.
From {A,C}: cheapest = C–D(1). Add D.
From {A,C,D}: cheapest = D–E(2). Add E.
From {A,C,D,E}: cheapest = B–C(3). Add B. Done.
Total = 2+1+2+3 = 8 ✓ (same as Kruskal's)

What to write in your book

Prim's: start at any vertex → add cheapest edge to new vertex → repeat until all included.
At each step: look only at edges from current tree to unvisited vertices.

Which does NOT describe Prim's algorithm?

Comparing the two algorithms

core concept

Both algorithms always produce a minimum spanning tree with the same total weight. The tree structure may differ if some edges have equal weights.

Feature	Kruskal's	Prim's
Starting point	Any edge (globally)	Specific vertex
Sort required?	Yes — sort all edges	No — compare locally
Best when	Edge list given	Diagram given
Total weight	Same result	Same result

HSC exam tip: Questions usually specify which algorithm to use. Show all steps clearly — partial working often scores marks even if you make a calculation error.

What to write in your book

Both algorithms give same total weight.
Kruskal's: sort globally, skip cycles. Prim's: grow from vertex, add nearest new vertex.
Show every step in working — partial marks available.

Complete: A minimum spanning tree of a 6-vertex weighted network has exactly _______ edges.

Worked examples · reveal each step

PROBLEM 1 · KRUSKAL'S ALGORITHM

5 vertices A–E. Edges: A–B(8), A–C(3), B–C(5), B–D(7), C–D(2), C–E(6), D–E(4). Find the MST using Kruskal's.

Sort edges: C–D(2), A–C(3), D–E(4), B–C(5), C–E(6), B–D(7), A–B(8)

List all edges from smallest to largest weight

PROBLEM 2 · PRIM'S ALGORITHM

Same network as Problem 1. Use Prim's algorithm starting at vertex A.

Start: Tree = {A}. Edges from A: A–B(8), A–C(3). Cheapest = A–C(3). Add C.

First step: add cheapest edge from starting vertex

PROBLEM 3 · CONTEXT QUESTION

A pipeline network connects towns P, Q, R, S with costs (km): P–Q: 12, P–R: 8, Q–R: 5, Q–S: 10, R–S: 7. What is the minimum total pipeline length to connect all towns?

Kruskal's: sort edges: Q–R(5), R–S(7), P–R(8), Q–S(10), P–Q(12)

Sort from cheapest — clear and systematic

Practice activity

+10 XP

Network: A–B(6), A–C(4), B–C(2), B–D(8), C–D(3), D–E(5). Use Kruskal's to find the MST and total weight.
Use Prim's starting at vertex B for the same network. Do you get the same total weight?
In Kruskal's, you try to add edge A–B but both A and B are already connected through C. What do you do?
A network has 8 vertices. Its MST has total weight 24. Another student claims they found an MST with weight 22. Who is right? How do you check?

auto-saved

Revisit your thinking

For the parks problem, the MST uses edges C–D(1), A–C(2), D–E(2), B–C(3) — total cost $8,000. The strategy of "always choose the cheapest available connection" is exactly Kruskal's or Prim's — you may have instinctively applied the algorithm!

auto-saved

Multiple choice

+5 XP per correct

Q1. Kruskal's algorithm adds edges in order of:

Q2. Prim's algorithm always:

Q3. In Kruskal's algorithm, you skip an edge when:

Q4. A minimum spanning tree of a 7-vertex weighted network has how many edges?

Q5. If you apply both Kruskal's and Prim's to the same weighted connected network:

Short answer

ApplyBand 43 marks

SA 1. Use Kruskal's algorithm to find the MST for: A–B(9), A–C(3), B–C(6), B–D(5), C–D(2), C–E(8), D–E(4). State which edges are in the MST and the total weight. (3 marks)

auto-saved

AnalyseBand 52 marks

SA 2. A student is using Prim's algorithm. They are at step 3 and their current tree is {A, C, D}. Available edges to new vertices: A–B(9), C–B(6), D–B(5), D–E(4). Which edge should they add next? Justify. (2 marks)

auto-saved

Answers (click to reveal)

MC 1 — A: Kruskal's sorts edges increasing weight.

MC 2 — D: Prim's grows from a starting vertex.

MC 3 — B: Skip when adding creates a cycle.

MC 4 — C: 7−1=6 edges.

MC 5 — A: Both produce the same total weight MST.

SA 1 (3 marks): Sorted correctly [1]; correct MST edges identified [1]; total weight = 14 [1].

SA 2 (2 marks): D–E(4) identified [1]; correctly justified as cheapest to new vertex [1].

Boss battle · The Pipeline Planner

earn bronze · silver · gold

Timed questions on Kruskal's and Prim's algorithms.

⚔ Enter the arena

Mark lesson as complete

Tick when you've finished.

← Lesson 4 · Trees and Spanning Trees Lesson 6 · Dijkstra's Algorithm →

Module overview · Maths Standard