Prim's algorithm finds a minimum spanning tree by starting at one vertex and repeatedly adding the lowest-weight edge that connects the growing tree to a new vertex. It stops when every vertex is connected.
A minimum spanning tree is a subgraph of a connected, weighted, undirected graph that connects every vertex, contains no cycles, and has the smallest possible total weight. This is HL-only content in AHL 3.16: Tree and cycle algorithms.
The Method
- Choose any starting vertex.
- Consider every edge joining a vertex already in the tree to a vertex outside it.
- Select an eligible edge with the smallest weight.
- Add that edge and its new vertex to the tree.
- Repeat until all vertices are included.
For a graph with vertices, the completed tree must contain exactly edges. Because each chosen edge introduces a new vertex, no cycle is created.
At each stage, the selected edge is locally cheapest among the eligible edges. Prim's algorithm nevertheless produces a globally minimum total because any cheaper spanning tree would need another edge crossing the same boundary, and that edge cannot be lighter than the chosen one.
Worked Example
Suppose the edges are , , , , and . Starting at :
| Stage | Eligible edges | Selected edge |
|---|---|---|
| Start at | ||
| Tree contains (A,B) |
The minimum spanning tree contains , , and , with total weight
The common misconception is to choose the cheapest edge anywhere in the graph. Prim's algorithm chooses the cheapest edge adjacent to the current tree that reaches a new vertex. If equal-weight choices occur, different minimum spanning trees may be possible.
Exam Technique
In an IB Mathematics AI HL response, record the edge-selection order, show the completed tree or list its edges, and calculate its total weight. A final weight without this certificate may not earn full credit when the command term is construct or determine.