Identify a tree and a spanning tree in a connected network, apply Prim's algorithm to build the minimum spanning tree of a weighted graph, and find its total weight

What this dot point is asking

VCAA wants you to find the cheapest way to connect every vertex of a weighted network. You recognise a tree (a connected graph with no cycles) and a spanning tree (a tree that includes every vertex), then apply Prim's algorithm to grow the minimum spanning tree edge by edge and total its weight. This is the optimisation tool for problems such as cabling, piping or road links where everything must be connected at least cost.

Trees and spanning trees

A connected graph with $n$ vertices has many possible spanning trees, but each one uses exactly $n - 1$ edges and contains no cycle. Adding any further edge to a spanning tree creates a cycle; removing any edge disconnects it. The minimum spanning tree is the spanning tree whose edge weights sum to the smallest possible total.

Prim's algorithm

Prim's algorithm grows the tree from a starting vertex:

1. Choose any vertex to start the tree.
2. Of all edges that join a vertex already in the tree to a vertex not yet in it, add the one with the smallest weight.
3. Reject any edge that would connect two vertices already in the tree (it would form a cycle).
4. Repeat until every vertex is included, which happens after $n - 1$ edges.

Reading Prim's from a table

When the network is given as a weighted distance table rather than a diagram, Prim's algorithm works the same way: start with one vertex's column, repeatedly pick the smallest unused weight in the rows of the chosen vertices that reaches a new vertex, and cross out columns as vertices join.

Why the greedy choice works

Prim's algorithm is greedy: at each step it adds the single cheapest edge that reaches a new vertex, never reconsidering earlier choices. It is not obvious that always grabbing the locally cheapest safe edge produces a globally cheapest tree, but it does, because any edge that is the lightest crossing between the set of vertices already in the tree and those outside must belong to some minimum spanning tree. This cut property guarantees the algorithm cannot paint itself into a corner. You do not need to prove this in VCE, but knowing the algorithm is provably optimal is reassuring: there is no need to check other trees once Prim's terminates.

Prim's from a weighted table

Many exam questions present the network as a weighted adjacency table rather than a diagram. The method is identical. Pick a starting vertex and highlight its column; then scan the rows of every vertex currently in the tree for the smallest weight that leads to a vertex not yet included, add that edge, and bring the new vertex into the tree by highlighting its column too. Cross out or ignore weights that would connect two vertices already in the tree, since those would form a cycle. Continue for $n - 1$ selections. Working from the table is often faster and less error-prone than tracing a cluttered diagram, and it makes the order of edge selection easy to record.

Minimum spanning tree versus shortest path

A frequent confusion is between the minimum spanning tree and the shortest path. The minimum spanning tree connects every vertex at least total cost and is the answer to "wire up all the sites cheaply", but the unique path it provides between two particular vertices is generally not the shortest route between them. Shortest path problems instead minimise the distance between one specified pair of vertices and may ignore most of the network. When a question asks to connect everything, use Prim's; when it asks for the quickest route from one place to another, use a shortest-path method. Reading which objective is wanted is half the marks.

Why this matters for the exams

Minimum spanning tree questions appear in most Networks exams and are reliable marks if you apply Prim's carefully and report both the edges chosen and the total weight. Markers check that the tree has $n - 1$ edges, no cycle, and includes every vertex. The technique contrasts with shortest path, which minimises the route between two specific vertices rather than connecting all of them.