Prim’s Algorithm: Minimum Spanning Tree

Problem: Minimum Spanning Tree (MST)

Given a connected, undirected, weighted graph, find a spanning tree with minimum total edge weight.

A spanning tree connects all $n$ vertices using exactly $n-1$ edges with no cycles.

Applications:
- Designing cheapest network (electrical grid, fibre optic cable, road networks)
- Cluster analysis
- Approximation algorithms for TSP

Algorithm Specification

Input: Connected, undirected, weighted graph $G = (V, E, w)$, starting vertex $s$
Output: A minimum spanning tree — a set of $n-1$ edges with minimum total weight
Precondition: Graph must be connected (otherwise no spanning tree exists)

Prim’s Algorithm (Greedy)

Prim’s grows the MST one edge at a time, always adding the cheapest edge connecting a vertex in the MST to a vertex outside it.

ALGORITHM Prim(graph, start)
    mst_edges ← empty set
    visited ← {start}
    pq ← PriorityQueue of edges from start (sorted by weight)

    while visited ≠ all vertices do
        (u, v, w) ← removeMin(pq)    // cheapest available edge
        if v NOT in visited then
            add (u, v, w) to mst_edges
            add v to visited
            for each edge (v, x, wx) where x NOT in visited do
                insert (v, x, wx) into pq
            end for
        end if
    end while
    return mst_edges

Worked Example

Graph with vertices {A, B, C, D} and edges:
- A–B: 4, A–C: 2, B–C: 1, B–D: 5, C–D: 8

Starting at A:
1. Visited: {A}. Available edges: (A–B, 4), (A–C, 2)
2. Add cheapest: A–C (weight 2). Visited: {A, C}
3. Available: (A–B, 4), (C–B, 1), (C–D, 8)
4. Add cheapest: C–B (weight 1). Visited: {A, B, C}
5. Available: (A–B, 4 — duplicate, skip), (B–D, 5), (C–D, 8)
6. Add cheapest: B–D (weight 5). Visited: {A, B, C, D} ✓

MST edges: {A–C, C–B, B–D}, total weight = 2 + 1 + 5 = 8

Correctness (Cut Property)

Prim’s correctness relies on the cut property:
For any cut (partition of vertices into two sets), the minimum-weight edge crossing the cut belongs to some MST.

At each step, Prim’s maintains a cut: {visited} vs {unvisited}. Adding the minimum edge across this cut is always safe (proven by contradiction: if a cheaper spanning tree existed, swapping would not reduce cost).

Time Complexity

For sparse graphs, heap-based Prim’s is much faster.

Limitations

• Requires connected graph: If the graph is disconnected, Prim’s produces a spanning tree only for the component containing the start vertex.
• Undirected graphs only: Defined for undirected weighted graphs.
• Non-negative weights not strictly required (works with negative weights, unlike Dijkstra’s for shortest path).

EXAM TIP: In exams, trace Prim’s step by step, showing the priority queue state, which edge is added, and the set of visited vertices at each step. Marks are awarded for correct tracing, not just the final answer.

VCAA FOCUS: Know the greedy nature of Prim’s and its connection to the cut property. Be able to argue why it produces a minimum spanning tree.