Prim's Algorithm

Prim's algorithm is the second important greedy algorithm for the Minimum-Spanning-Tree (MST) problem after Kruskal's algorithm.

The central idea is quite different from Kruskal's:

Kruskal grows a forest by considering edges globally, whereas Prim grows one single tree starting from a chosen root vertex.

Prim's algorithm is also closely related to Dijkstra's algorithm, although the quantity being minimized is different.

---

1. Basic Idea

Suppose we have a connected, undirected, weighted graph.

Prim's algorithm:

1. Select an arbitrary vertex as the root.
2. Start the MST with this vertex.
3. Among all edges connecting the current tree to a vertex outside the tree, choose the minimum-weight edge.
4. Add that edge and the new vertex to the tree.
5. Repeat until all vertices are included.

So we can visualize the process as:

             Start with one vertex
                     │
                     ▼
              Current MST
                     │
                     ▼
       Find cheapest edge connecting
       MST to an outside vertex
                     │
                     ▼
              Add edge + vertex
                     │
                     ▼
              Larger MST
                     │
                     ▼
                 Repeat
                     │
                     ▼
            All vertices included

Growing a single tree from an arbitrary root vertex. At every step, a light edge crossing the cut between the vertices already in the tree and the remaining vertices is selected.

---

2. A Simple Example

Consider this graph:

             4
        A -------- B
        |          |
       2|          |5
        |          |
        C -------- D
             3

The edges are:

Edge	Weight
A-C	2
C-D	3
A-B	4
B-D	5

Let us choose A as the starting/root vertex.

---

Step 1: Start with A

       A

The current tree contains only:

A

Edges leaving A are:

A-C = 2
A-B = 4

The cheapest is:

A-C = 2

So we add it.

---

Step 2: Add C

The tree is now:

       A
       |
       C

The vertices outside the tree are:

B, D

Edges connecting the current tree {A,C} to outside vertices are:

A-B = 4
C-D = 3

The cheapest is:

C-D = 3

Add C-D.

---

Step 3: Add D

Now:

       A
       |
       C
       |
       D

The only remaining vertex is B.

Edges connecting the current tree to B:

A-B = 4
D-B = 5

Choose:

A-B = 4

---

Step 4: Final MST

We obtain:

                    4

       A -------- B
       |
      2|
       |
       C
       |
      3|
       |
       D

The selected edges are:

(A,C) = 2
(C,D) = 3
(A,B) = 4

Total weight:

2 + 3 + 4 = 9

Therefore, the MST has total weight 9.

---

3. The Important Concept: The Cut

The key concept in Prim's algorithm is a cut.

Suppose the current tree contains:

{A, C}

and the remaining vertices are:

{B, D}

We can divide the graph into two groups:

       CURRENT TREE        OUTSIDE
       {A, C}              {B, D}
          │                   │
          └────── CUT ────────┘

The edges crossing this cut are:

A-B = 4
C-D = 3

The light edge crossing the cut is:

C-D = 3

Therefore Prim chooses C-D.

This is the theoretical basis of the algorithm.

---

4. Why Is Prim's Choice Safe?

This is where the greedy property comes in.

At every step, Prim chooses a light edge crossing the current cut.

such a light edge is a safe edge for the current partial tree.

Therefore:

Light edge
     ↓
Safe edge
     ↓
Can be added to MST

This is why Prim's greedy choices lead to an MST.

---

5. Prim vs Kruskal

This distinction is very useful for students.

Kruskal

Kruskal starts with:

V separate trees

and gradually combines them.

{A} {B} {C} {D} {E}
 ↓
{A,B} {C} {D,E}
 ↓
{A,B,C} {D,E}
 ↓
{A,B,C,D,E}

So Kruskal maintains a forest.

---

Prim

Prim starts with:

One vertex

and grows one tree.

{A}
 ↓
{A,B}
 ↓
{A,B,C}
 ↓
{A,B,C,D}
 ↓
{A,B,C,D,E}

So Prim maintains one connected tree throughout.

The key difference

Kruskal	Prim
Starts with separate trees	Starts with one vertex
Maintains a forest	Maintains one tree
Selects globally smallest suitable edge	Selects smallest edge leaving current tree
Uses disjoint sets	Uses a min-priority queue
Edge-oriented	Vertex/tree-growth oriented

---

6. How Does Prim Know Which Edge to Choose?

This is where the min-priority queue is used.

For every vertex that is not yet in the tree, Prim maintains a value called:

v.key

v.key represents:

The minimum weight of an edge connecting vertex v to a vertex already in the tree.

If no such edge currently exists, its key is:

∞

Each vertex also has:

v.π

which stores the vertex that will be the parent of v in the MST.

---

7. Example of Key Values

Suppose Prim has started with A.

Initially:

A     B     C     D

We set:

A.key = 0
B.key = ∞
C.key = ∞
D.key = ∞

A is chosen first because it has the smallest key.

After processing A:

A-B = 4
A-C = 2

Therefore:

B.key = 4
B.π = A

C.key = 2
C.π = A

So:

       A
      / \
     /   \
   4/     \2
   B       C

The minimum key is C:

C.key = 2

So C is selected next.

After processing C, we discover:

C-D = 3

Therefore:

D.key = 3
D.π = C

Now the keys are:

B.key = 4
D.key = 3

D is selected next.

This continues until all vertices are included.

---

8. Prim's Algorithm — Pseudocode

MST-PRIM(G, w, r)

1. for each vertex u ∈ G.V
2.      u.key = ∞
3.      u.π = NIL

4. r.key = 0

5. Q = ∅

6. for each vertex u ∈ G.V
7.      INSERT(Q, u)

8. while Q ≠ ∅
9.      u = EXTRACT-MIN(Q)

10.     for each vertex v ∈ Adj[u]

11.         if v ∈ Q and w(u,v) < v.key

12.              v.π = u

13.              v.key = w(u,v)

14.              DECREASE-KEY(Q, v, w(u,v))

This is the implementation using a min-priority queue.

---

9. Understanding the if Condition

The most important part for students is:

if v ∈ Q and w(u,v) < v.key

It means:

Condition 1

v ∈ Q

means:

v has not yet been added to the MST.

Condition 2

w(u,v) < v.key

means:

We have found a cheaper edge for connecting v to the current tree.

If both conditions are true:

v.π = u
v.key = w(u,v)

So we update the best known connection for v.

---

10. What Does DECREASE-KEY Mean?

Suppose:

B.key = 7

and later we discover an edge:

A-B = 4

Then 4 is a better way to connect B to the current tree.

So:

B.key = 4

This operation is called:

DECREASE-KEY

The priority queue is then updated so that B gets a higher priority for extraction.

---

11. Why Does Prim Need a Priority Queue?

Suppose there are 1,000 vertices outside the tree.

At every step we need to find:

Which outside vertex has the smallest key?

Searching all 1,000 vertices every time would be expensive.

A min-priority queue allows us to efficiently perform:

EXTRACT-MIN

to obtain the vertex with the smallest key.

It also supports:

DECREASE-KEY

when we discover a cheaper connection.

---

12. Complexity Analysis

The running time of Prim's algorithm depends on the implementation of the min-priority queue.

For the standard implementation using a binary heap:

Initialization

We initialize the vertices and insert them into the priority queue.

This takes:

O(V log V)

---

Extract-Min

We perform one EXTRACT-MIN for each vertex.

There are:

V EXTRACT-MIN operations

Each takes:

O(log V)

Therefore:

O(V log V)

---

Decrease-Key

During the algorithm, edges are examined.

There can be at most:

E DECREASE-KEY operations

Each takes:

O(log V)

Therefore:

O(E log V)

---

Total

Therefore:

O(V log V)
+ O(E log V)
+ O(E)

which simplifies to:

O(ElogV)​

for the binary-heap implementation.

This is the bound for Prim's algorithm using a binary heap.

---

13. Prim with Fibonacci Heap

An improved implementation using a Fibonacci heap.

With a Fibonacci heap:

• EXTRACT-MIN is more expensive amortized
• DECREASE-KEY is much cheaper

The resulting complexity is:

O(E+VlogV)​

This is asymptotically better than O(E log V) when the graph is sufficiently dense.

---

14. Complexity Summary

Implementation	Time Complexity
Simple array	O(V²)
Binary heap	O(E log V)
Fibonacci heap	O(E + V log V)

For undergraduate students, the most important result to remember is:

Prim’s algorithm using a binary heap: O(ElogV)​

---

⭐ Final Takeaway

The easiest way for students to remember Prim's algorithm is:

Start from any vertex and continuously add the cheapest edge that connects the current MST to a vertex outside the MST.

Or even more simply:

Prim = Grow ONE tree

Kruskal = Join MANY trees

And the main complexity result is:

O(ElogV)​

when a binary heap is used as the min-priority queue.

Example Problem