C++UCS301
Graphs & ApplicationsC++17

Prim’s MST

Prim grows one minimum spanning tree by repeatedly adding the cheapest edge crossing from the tree to an outside vertex.

What to understand

  • Cut property
  • Min-priority queue
  • Key values
  • Dense versus sparse implementations

Remember this

  1. 1Works on connected weighted undirected graphs
  2. 2Similar structure to Dijkstra but different key meaning
  3. 3Produces V−1 edges

Detailed notes

Prim maintains one growing tree and repeatedly chooses the cheapest edge crossing the cut between included and excluded vertices. The cut property guarantees that a minimum crossing edge is safe for some MST.

A sparse implementation keeps candidate edges in a min heap. A key-array variant tracks the best known connection for each outside vertex and resembles Dijkstra structurally, though the key is one edge cost rather than a source distance.

How it works

  1. 1Start from any vertex with cost zero.
  2. 2Extract the cheapest connection to an unused vertex.
  3. 3Accept it and add its cost once.
  4. 4Offer all outgoing edges to unused neighbours.

Worked trace

Grow an MST cut

From A: A-B=2, A-C=5; B-C=1
  1. 1Start with A in the tree.
  2. 2The cheapest crossing edge is A-B with weight 2; add B.
  3. 3Now B-C with weight 1 also crosses the cut.
  4. 4Choose B-C rather than A-C.
Result: MST edges A-B and B-C; total weight 3

Where it is used

  • Minimum-cost connected infrastructure
  • Network cabling and pipeline layout
  • Clustering and approximation subroutines

Common mistakes

  • Running only once on a disconnected graph and calling the result an MST
  • Adding the same vertex cost more than once
  • Confusing cumulative Dijkstra distance with Prim's single-edge key

Complexity analysis

OperationBestAverageWorstExtra space
MSTO(E log V)O(E log V)O(E log V)O(V+E)

C++ implementation

C++17 reference
main.cpp

Prim using a min-priority queue

Each queue item stores edge cost, destination, and parent so selected MST edges can be recovered.

long long prim(const vector<vector<pair<int, int>>>& graph) {
    using Edge = tuple<int, int, int>; // weight, vertex, parent
    priority_queue<Edge, vector<Edge>, greater<Edge>> pending;
    vector<bool> used(graph.size(), false);
    pending.push({0, 0, -1});
    long long total = 0;

    while (!pending.empty()) {
        auto [weight, current, parent] = pending.top(); pending.pop();
        if (used[current]) continue;
        used[current] = true;
        total += weight;
        for (auto [next, edgeWeight] : graph[current])
            if (!used[next]) pending.push({edgeWeight, next, current});
    }
    return total;
}
17 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.