NSWMaths Standard 2Syllabus dot point

What is a minimum spanning tree, and how is it found using Prim's or Kruskal's algorithm?

Find a minimum spanning tree for a weighted graph using Prim's or Kruskal's algorithm

A focused answer to the HSC Maths Standard 2 dot point on minimum spanning trees. Definition of a spanning tree and minimum spanning tree, step-by-step Prim's and Kruskal's algorithms, and worked examples for utility networks and rural Australian infrastructure planning.

Generated by Claude OpusReviewed by Better Tuition Academy8 min answerUpdated 2026-05-20

Have a quick question? Jump to the Q&A page

What this dot point is asking

NESA wants you to find a minimum spanning tree of a weighted graph using either Prim's or Kruskal's algorithm, showing each step clearly. The MST is the most common network optimisation question in the HSC.

The answer

Spanning tree

A spanning tree of a connected graph is a subgraph that:

includes every vertex of the original graph,
is connected (every pair of vertices linked by a path),
has no cycles.

A spanning tree on $n$ vertices always has exactly $n - 1$ edges.

Minimum spanning tree (MST)

A minimum spanning tree is a spanning tree with the smallest total edge weight among all possible spanning trees of the graph.

For a weighted graph (where each edge has a cost, distance or time), the MST connects all vertices using the least total weight.

Applications: laying the shortest total length of pipe, cable, fibre, or road to connect a set of locations.

Prim's algorithm

Prim's algorithm builds the MST one vertex at a time, growing outward from a chosen starting vertex:

Pick any starting vertex; this is the initial tree.
From all edges that connect a tree vertex to a non-tree vertex, choose the one with the smallest weight.
Add that edge and the new vertex to the tree.
Repeat until all vertices are in the tree.

Prim's adds $n - 1$ edges in total (one per added vertex after the first).

Kruskal's algorithm

Kruskal's algorithm sorts all edges and adds them in order, skipping any that create a cycle:

List all edges in order of increasing weight.
Take the cheapest unused edge; if it does not create a cycle with edges already chosen, add it.
Repeat until $n - 1$ edges are added.

Both algorithms always produce a minimum spanning tree, though the exact edges may differ if there are ties in weight.

Which to use

Prim's is easier when there are many edges (you only consider edges from the current tree).
Kruskal's is easier when edges are pre-sorted (just go down the list, checking for cycles).

The HSC accepts either; show your working clearly so the marker can follow which algorithm you used.

Cycle check (Kruskal's)

An edge creates a cycle if both endpoints are already connected (directly or via existing tree edges). For small graphs you can spot this visually; for larger graphs, keep track of which vertices are in which component as you add edges.

Worked example

Prim's, step by step

A network has $5$ vertices and the following edge weights:

Edge	Weight
IMATH_1	IMATH_2
IMATH_3	IMATH_4
IMATH_5	IMATH_6
IMATH_7	IMATH_8
IMATH_9	IMATH_10
IMATH_11	IMATH_12
IMATH_13	IMATH_14

Start Prim's from $A$ .

Step 1: Tree = $\{A\}$ . Cheapest edge from tree: $AC$ (weight $2$ ). Add.

Step 2: Tree = $\{A, C\}$ . Cheapest external edge: $CD$ (weight $3$ ). Add.

Step 3: Tree = $\{A, C, D\}$ . Cheapest external edge: $AB$ (weight $4$ ). Add. ( $BD$ at $10$ and $DE$ at $6$ are both larger.)

Step 4: Tree = $\{A, B, C, D\}$ . Cheapest external edge: $DE$ (weight $6$ ). Add. ( $CE$ at $7$ is larger.)

Final MST: $AC, CD, AB, DE$ . Total weight: $2 + 3 + 4 + 6 = 15$ .

Kruskal's on the same network

Sort all edges by weight: $AC(2), CD(3), AB(4), BC(5), DE(6), CE(7), BD(10)$ .

Add $AC$ : tree = $\{AC\}$ .

Add $CD$ : tree = $\{AC, CD\}$ . Connects $A, C, D$ .

Add $AB$ : tree = $\{AC, CD, AB\}$ . Connects $A, B, C, D$ .

Skip $BC$ : would create cycle $A$ - $B$ - $C$ - $A$ via existing edges.

Add $DE$ : tree = $\{AC, CD, AB, DE\}$ . Connects all $5$ vertices. Done.

Total: $2 + 3 + 4 + 6 = 15$ . Same as Prim's.

Australian context

A regional NSW council wants to lay fibre optic cable connecting $6$ small towns. The possible routes follow existing roads with known lengths. Total available routes: $9$ edges between the $6$ town vertices. The MST gives the minimum total cable needed: $6 - 1 = 5$ edges, total length determined by the specific weights.

This is a real-world optimisation problem solved by either algorithm. The MST is also the model for water mains, electricity distribution, gas pipelines and similar utility networks where reliability of one path per pair is acceptable.

Past exam questions, worked

Real questions from past NESA papers on this dot point, with our answer explainer.

2022 HSC Q225 marksA network has

6

vertices and weighted edges connecting them. Use Prim's algorithm starting from vertex

A

to find a minimum spanning tree. Show your work. (Weights given in the question.)

Show worked answer →

Prim's algorithm steps:

Step 1: Start with $A$ . Add the cheapest edge from $A$ to any other vertex, say $A$ - $C$ with weight $3$ .

Step 2: From the current tree $\{A, C\}$ , find the cheapest edge connecting to a vertex not yet in the tree. Say $C$ - $D$ with weight $4$ .

Step 3: Continue. From $\{A, C, D\}$ , the cheapest external edge might be $D$ - $B$ with weight $5$ .

Step 4: From $\{A, B, C, D\}$ , the cheapest external edge might be $B$ - $E$ with weight $6$ .

Step 5: From $\{A, B, C, D, E\}$ , the cheapest external edge might be $E$ - $F$ with weight $7$ .

Final MST: edges $AC, CD, DB, BE, EF$ , total weight $3 + 4 + 5 + 6 + 7 = 25$ .

Markers reward a clear step-by-step working, the edges in order added, no edges that form cycles, and the final total weight. The exact edges depend on the network in the question.

2023 HSC Q244 marksA water utility wants to connect

5

towns with the minimum total length of pipeline. The possible pipeline routes and lengths (in km) form a weighted graph. Find the minimum spanning tree and its total length.

Show worked answer →

Sort all edges by weight (Kruskal's algorithm). Add them in order from smallest to largest, but skip any edge that would create a cycle.

For $5$ towns, the MST has $5 - 1 = 4$ edges.

Worked example with hypothetical weights: edges sorted $AB(8), CD(10), AC(12), BD(15), DE(18), \ldots$ .

Add $AB(8)$ : tree $\{AB\}$ .

Add $CD(10)$ : tree $\{AB, CD\}$ . Disconnected, but no cycle yet.

Add $AC(12)$ : tree $\{AB, CD, AC\}$ . Now connects the two components.

Skip $BD(15)$ if it would create a cycle in $\{ABCD\}$ . (It does: $A$ - $B$ - $D$ and $A$ - $C$ - $D$ both exist.) Skip.

Add $DE(18)$ : tree $\{AB, AC, CD, DE\}$ . All $5$ vertices connected.

Total: $8 + 10 + 12 + 18 = 48$ km.

Markers reward sorting, the cycle-check at each step, and the total weight with units.