How do we connect every site in a network at the least total cost?
Solve connector problems by finding a minimum spanning tree using Prim's algorithm and interpret its total weight.
How to solve a connector problem by finding a minimum spanning tree with Prim's algorithm, confirm it has n minus 1 edges, and interpret its total weight as the least connection cost.
Reviewed by: AI editorial process; not yet individually human-reviewed
Have a quick question? Jump to the Q&A page
Jump to a section
What this dot point is asking
You must apply Prim's algorithm, recognise the tree has edges, and interpret the total weight as the minimum connection cost.
The connector problem
A connector problem asks how to join every site (cable, pipe, road) so all are connected for the least total cost. The solution is a minimum spanning tree (MST): a spanning tree of least total weight.
Prim's algorithm
Prim's algorithm grows the tree from a starting vertex.
Choosing the cheapest edge leaving the current set each time guarantees the minimum total, and refusing cycles keeps it a tree.
Interpreting the result
The total weight of the MST is the least cost to connect every site. Note that an MST is not always unique: if two edges tie, different valid trees of the same total weight can result, and either is acceptable.