How do we connect every site in a network at the lowest total cost?
Find minimum spanning trees of weighted networks using a systematic algorithm.
Trees, spanning trees and minimum spanning trees, with Prim's algorithm applied to the minimum connector problem in TCE Mathematics Applications.
Reviewed by: AI editorial process; not yet individually human-reviewed
Have a quick question? Jump to the Q&A page
What this dot point is asking
The minimum connector problem asks how to link every site, such as towns to be joined by cable or pipe, using the least total length or cost. The answer is a special subgraph called a minimum spanning tree.
Minimum spanning tree
A network usually has many spanning trees. The minimum spanning tree (MST) is the one with the smallest total edge weight. It is the cheapest way to connect everything while never forming a loop, because a loop would add cost without connecting any new vertex.
Building it with Prim's algorithm
A reliable systematic method is to grow the tree one vertex at a time. Start anywhere, then repeatedly add the cheapest edge that joins a new vertex to the part already built, never closing a loop.
Notice the edges A-B (4) and C-D (6) were never used; adding either would create a cycle or cost more than the edge already chosen for that connection.
Reading the answer
The exam usually wants both the set of edges in the MST and its total weight. State the edges clearly and add their weights for the total, which is the minimum cost to connect the network.
Kruskal's algorithm as an alternative
Prim's algorithm grows one connected tree from a starting vertex, but Kruskal's algorithm offers a different route to the same minimum spanning tree. Instead of growing from one point, Kruskal's sorts all the edges from cheapest to dearest and adds them one at a time, skipping any edge that would close a cycle, until edges have been chosen. The two methods always reach the same total weight on a network with distinct edge weights, so you can use whichever the question suggests or use one to check the other.
When edge weights repeat
If two edges share the same weight, a network can have more than one minimum spanning tree, all with the same total weight. The exam accepts any valid MST in that case, provided it connects every vertex, contains no cycle, and uses exactly edges. State your tree clearly so the marker can verify it.
A complete answer lists the edges of the minimum spanning tree, confirms it uses exactly edges and contains no cycle, and states the minimum total weight interpreted in the units of the problem.
Exam-style practice questions
Practice questions written in the style of TASC exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.
TCE 20216 marksAn array of garden sprinklers (S1 to S7) is connected by pipes to a tap; the graph shows distances in metres. a) Using Prim's algorithm, show how all the sprinklers and tap connect with the minimum pipe length. b) What is the minimum total length of pipe? c) A gardener charges \22.50$ per metre. A pipe already exists between the tap and S3. Find the amount to charge for connecting the array.Show worked answer →
a) (2 marks) Apply Prim's algorithm: start at any vertex (say the tap), then repeatedly add the shortest edge that connects a new vertex to the tree already built, never forming a cycle, until all 8 vertices are joined. Mark the selected edges; they form the minimum spanning tree.
b) (1 mark) Add the lengths of the edges chosen in part a). That total is the minimum pipe length needed.
c) (3 marks) Because the tap-to-S3 pipe already exists, that length need not be laid. Subtract the tap-to-S3 edge length from the minimum total, then multiply the remaining length by per metre to get the amount to charge.
TCE 20194 marksSix towns A to F are to be linked by fibre cable. The connection lengths (km) are A-B 5, A-C 7, B-C 4, B-D 6, C-E 8, D-E 3, D-F 9, E-F 2. a) Use Prim's algorithm starting at A to find the minimum spanning tree. b) State its total length and how many edges it uses.Show worked answer →
a) (3 marks) Start at A. Cheapest from A is A-B (5); tree {A, B}. Cheapest joining a new vertex is B-C (4); tree {A, B, C}. Next is B-D (6); tree {A, B, C, D}. Next is D-E (3); tree {A, B, C, D, E}. Next is E-F (2); tree {A, B, C, D, E, F}. Skip A-C, C-E, D-F as they would add cost or a cycle.
b) (1 mark) Edges A-B, B-C, B-D, D-E, E-F. Total km, using edges for vertices. Markers reward never closing a cycle and stopping at edges.