###### Books / Analysis of Algorithms / Chapter 20

# Minimum Spanning Trees - Prim's Algorithm

An alternative algorithm for finding MST’s is *Prim’s algorithm* which runs asymptotically faster than Kruskal’s algorithm, but at the price of requiring a queue data structure.

## Prim’s Algorithm

*Prim’s algorithm* finds MST’s by *growing the MST* by adding light edges between the current tree and other vertices. The vertices are stored in a minimum *priority queue* based on the smallest weigh edge connecting vertices currently not in the tree with a vertex in the tree.

**Algorithm**

```
MST-PRIM(G,w,r)
1. for each u ∈ G.V
2. u.key = ∞
3. u.pi = NIL
4. r.key = 0
5. Q = G.V
6. while Q ≠ ∅
7. u = EXTRACT-MIN(Q)
8. for each v ∈ G.Adj[u]
9. if v ∈ Q and w(u,v) < v.key
10. v.pi = u
11. v.key = w(u,v)
```

Basically the algorithm works as follows:

- Initialize
Qand set the source (root) key to 0- While
Qis not empty, dequeue the vertex with minimum weight edge and add it to the tree by adding edge (u.π,u) toT- For each vertex
vin Adj[u] that is still inQ, check ifw(u,v)(the edge weights fromufor all vertices not inT) are less than the currentv.key(the current smallest edge weight) and if so update the predecessor and key fields

The run time of Prim’s algorithm depends on the implementation of the priority queue, but can be made to run in O(*E* + *V* lg *V*) using a *Fibonacci heap* for the priority queue.

**Example**

Using the same undirected graph from chapter 19

We will (arbitrarily) initialize *Q* with vertex 1 giving

*Step 1*: Dequeue vertex 1 and update *Q* (and reprioritizing) by changing *u*_{3}*.key* = 2 (edge (*u*_{1},*u*_{3})), *u*_{2}*.key* = 3 (edge (*u*_{1},*u*_{2})), *u*_{4}*.key* = 6 (edge (*u*_{1},*u*_{4}))

*Step 2*: Dequeue vertex 3 (adding edge (*u*_{1},*u*_{3}) to *T*) and update *Q* (and reprioritizing) by changing *u*_{4}*.key* = 4 (edge (*u*_{3},*u*_{4}))

*Step 3*: Dequeue vertex 2 (adding edge (*u*_{1},*u*_{2}) to *T*) and update *Q* (and reprioritizing) by changing *u*_{5}*.key* = 2 (edge (*u*_{2},*u*_{5}))

*Step 4*: Dequeue vertex 5 (adding edge (*u*_{2},*u*_{5}) to *T*) with no updates to *Q*

*Step 5*: Dequeue vertex 4 (adding edge (*u*_{3},*u*_{4}) to *T*) with no updates to *Q*

At this point *Q* = ∅ giving the final MST

with total weight 11.