Skip to main content
VICGeneral MathematicsSyllabus dot point

What is a spanning tree, and how does Prim's algorithm find the minimum spanning tree that connects every vertex at least cost?

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

A focused answer to the VCE General Mathematics Unit 4 Networks key-knowledge point on minimum spanning trees. The definition of a tree and spanning tree, the n minus 1 edge rule, applying Prim's algorithm step by step, and computing the minimum total weight.

Generated by Claude Opus 4.76 min answer

Reviewed by: AI editorial process; not yet individually human-reviewed

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

Jump to a section
  1. What this dot point is asking
  2. Trees and spanning trees
  3. Prim's algorithm
  4. Reading Prim's from a table
  5. Why this matters for the exams

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 nn vertices has many possible spanning trees, but each one uses exactly n−1n - 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−1n - 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 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−1n - 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.