Prim's algorithm

Prerequisites

• Kruskal's algorithm and minimum spanning trees.
• Dijkstra: Prim has the same structure.
• Priority queue.

The analogy

How it works

Precondition: an undirected, connected, weighted graph. Negative weights are fine.

Start with one run by hand

Start at A. key[v] is the cheapest edge from the tree to v (∞ if none). Each round, add the outside vertex with the smallest key and update its neighbours' keys. Predict, then open "Check".

Finish the picture: a different start

Run Prim again starting from D.

• The first two additions. Predict them.
  Check

  From D: C (2) is cheapest. From {D, C}: B (3), since key[A] is 4 via C.

• The last addition and total. Predict both.
  Check

  A joins via B (1). Edges C–D, B–C, A–B: total 6 again. The start changes the order, not the tree here.

The rule in plain words

Start with any vertex in the tree. Set key of each vertex to its edge weight to the tree (∞ if none).

Repeat $V - 1$ times: add the outside vertex with the smallest key, then lower its neighbours' keys where its edges are cheaper.

The code

Read this code after you have done the run by hand. It will make more sense.

int prim(int w[][4], int n) {                    /* w = 0: no edge; returns MST weight */
    int key[100];
    int in_tree[100];
    int total = 0;
    for (int i = 0; i < n; i++) { key[i] = i == 0 ? 0 : INT_MAX; in_tree[i] = 0; }   /* start at 0 */
    for (int round = 0; round < n; round++) {
        int u = -1;
        for (int i = 0; i < n; i++)                  /* cheapest edge into the tree */
            if (!in_tree[i] && (u == -1 || key[i] < key[u])) u = i;
        in_tree[u] = 1; total += key[u];
        for (int v = 0; v < n; v++)                  /* u's edges may be cheaper now */
            if (w[u][v] && !in_tree[v] && w[u][v] < key[v]) key[v] = w[u][v];
    }
    return total;
}

flowchart TD
  A["tree = start vertex"] --> B["pick the outside vertex with the smallest key"]
  B --> C["add it and its key edge to the tree"]
  C --> D["lower the keys of its outside neighbours"]
  D --> E{"all vertices in the tree?"}
  E -->|no| B
  E -->|yes| F["done: minimum spanning tree"]
          

How fast is it?

The array version scans all vertices each round; the heap version pays $\log V$ per key update:

On a dense graph, $E \approx V^2$, so the simple array version is the better choice.

Common mistakes

• Updating keys with key[u] + w as in Dijkstra.
• Updating vertices already in the tree.
• Choosing the cheapest edge anywhere in the graph, which is Kruskal, instead of the cheapest edge leaving the tree.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• Prim always adds the cheapest edge leaving the tree because that edge is safe to include in a minimum spanning tree.
• It keeps one connected tree because every new vertex attaches to the existing tree.
• The array version is $O(V^2)$ because each of $V$ rounds scans all vertices for the smallest key.
• It differs from Dijkstra because its key is one edge weight, not a total distance.
• Any start vertex works because every vertex must be in the spanning tree anyway.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is Prim's algorithm like mould spreading?
   Sample answer

   It grows from one spot, each time covering the cheapest gap next to what it already covers, never starting a separate patch.

2. Walk through Prim from A on A–B 1, C–D 2, B–C 3, A–C 4, B–D 5.
   Sample answer

   Add A; then B (key 1); then C (key 3 via B); then D (key 2 via C). Total 6.

3. Why does the code compare w[u][v] < key[v] and not key[u] + w[u][v] < key[v]?

   A good answer says what the key means.

   Sample answer

   The key is the cost of the single edge that would attach v to the tree, not a path length. Adding key[u] would turn the algorithm into Dijkstra.

4. So what is Prim's algorithm, in one sentence?
   Sample answer

   It builds a minimum spanning tree by growing one tree from a start vertex, always adding the cheapest edge to a new vertex.

5. Why does starting from a different vertex still give a minimum spanning tree?
   Sample answer

   Every vertex ends up in the tree, and at every step the cheapest edge leaving the current tree is safe, whatever the tree started from.

6. What are Prim's array and heap costs?
   Sample answer

   Array: $O(V^2)$. Binary heap: $O((V + E) \log V)$. $O(V)$ extra space.

7. Why can a shortest-path tree differ from a minimum spanning tree?

   A good answer uses the triangle S–A 2, S–B 2, A–B 1.

   Sample answer

   Shortest paths from S keep S–A and S–B (each distance 2), total 4. The MST only needs S–A and A–B, total 3. One minimises distance from S, the other total edge weight.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the heap analysis and the history. I'd keep the mould analogy, the run from A, and "cheapest edge leaving the tree, like Dijkstra but with edge weights, $O(V^2)$ or $O(E \log V)$".

External resources

• VisuAlgo: Minimum spanning tree: run Prim from any start vertex.
• GeeksforGeeks: Prim's algorithm: array and heap versions.
• Wikipedia: Prim's algorithm: history and complexity.

Videos

• YouTube search: Prim's algorithm: pick a walkthrough with the key table.