# Prim’s Algorithm

## Introduction to Prim’s Algorithm

Prim’s algorithm is a greedy approach to find a minimum spanning tree from weighted, connected, undirected graph. It is a variation of Dijkstra’s algorithm. Working principle of Prim’s algorithm is very simple and explained here:

Initialize list of unvisited vertices with U_{V} = {V_{1}, V_{2}, V_{3}, . . . , V_{n}}

1. Select any arbitrary vertex from input graph G, call that subgraph as partial MST. Remove selected vertex from U_{V}

2. Form a set N_{E} – a set of unvisited neighbour edges of all vertices present in partial MST

3. Select an edge *e = (u, v)* from N_{E} with minimum weight, and add it to partial MST if it does not form a cycle and it is not already added.

If the addition of edge *e* forms a cycle, then skip that edge and select next minimum weight edge from N_{E}. Continue this procedure until we get an edge *e* which does not form a cycle. Remove corresponding added vertices *u* and *v* from U_{V}

4. Go to step 2 and repeat the procedure until U_{V }is empty.

Prim’s algorithm is preferred when the graph is dense with V << E. Kruskal performs better in the case of the sparse graph with V ≣ E.

## Algorithm for Prim’s Algorithm

Algorithm for Prim’s approach is described below :

**Algorithm **PRIM_MST(G, n)
// Description : Find MST of graph G using Prim’s algorithm
// Input : Weighted connected graph G and number of vertices n
// Output : Minimum spanning tree MST and weight of it i.e. cost
cost ← 0
// Initialize tree nodes
**for **i ← 0 to n – 1 **do
**MST[i] ← 0
**end**
MST[0] ← 1 // 1 is the initial vertex
**for **k ← 1 to n **do**
min_dist ← ∞
**for **i ← 1 to n – 1 **do**
**for **j ← 1 to n – 1 **do**
**if **G[i, j] and ((MST[i] AND ¬MST[j]) or (¬MST[i] AND MST[j])) **then**
if G[i, j] < min_dist then
min_dist ← G[i, j]
u ← i
v ← j
**end**
**end**
**end**
**end**
**print **(u, v, min_dist)
MST[u] ← MST[v] ← 1
cost ← cost + min_dist
**end**
**print **(“Total cost = ”, cost)

## Complexity Analysis of Prim’s Algorithm

- In every phase, algorithm search for minimum weight edge. Running time of algorithm heavily depends on how efficiently it performs search operation.
- The time taken by the algorithm can be computed as,

Rewriting the equation,

- The straight-forward approach to this is to search the entire adjacency matrix for each vertex. It takes O(|V|
^{2}) time for |V| vertices and |E| edges, where |V| represents a number of vertices, i.e. n. - However, with the help of some other data structures, we can improve the performance. Using binary heap and adjacency list, time can be reduced to O( |E| log |V| )
- Using the Fibonacci heap and adjacency matrix, performance can be improved to O(|E| + |V| log |V|).

## Example

**Problem: Find the cost of minimum spanning tree of the given graph by using Prim’s algorithm.**

**Solution:**

- Initialize U
_{V}– list of unvisited vertices – with all vertices in given graph. - Prim’s algorithm adds some arbitrary vertex V
_{x }from U_{V }to the partial solution and removes V_{x}from U_{V}. - N
_{E}-set of all neighbour edges of vertices in partial solution is explored. - The neighbour edge with minimum cost is added to the partial solution if it does not form a cycle and has not already been added to the partial solution.
- Otherwise, select the next minimum cost edge and add it to the partial solution and remove it from the list of unvisited vertices U
_{V}. - This process is repeated until all vertices are visited, i.e. U
_{V}becomes empty. - For given graph, initially the set of unvisited vertices U
_{V}= {a, b, c, d, e, f }.

Partial solution | Set of neighbour edges N_{E} | Cost of neighbour edges | Updated U_{V} |

Step 1 : U_{V} = {a, b, c, d, e, f}. Let us start with arbitrary vertex a. Initial partial solution | <a, b> <a, f> <a, e> | 3 5 6 | { b, c, d, e, f} |

Step 2 : Edge <a, b> has minimum cost, so add it. | <a, f> <a, e> <b, c> <b, f> | 5 6 1 4 | { c, d, e, f} |

Step 3 : Edge <b, c> has a minimum cost, so add it. | <a, f> <a, e> <b, f> <c, f> <c, d> | 5 6 4 4 6 | { d, e, f} |

Step 4 : Edge <b, f> and <c, f> have same minimum cost, so we can add any of it. Let us add <c, f> | <a, f> <a, e> <b, f> <c, d> <f, d> <f, e> | 5 6 4 6 5 2 | { d, e } |

Step 5 : Edge <f, e> has a minimum cost, so add it. | <a, f> <a, e> <b, f> <c, d> <f, d> | 5 6 4 6 5 | { d } |

Step 6 : Edge <b, f> has minimum cost, but its inclusion in above partial solution creates cycle, so skip edge <b, f> and check for next minimum cost edge i.e. <a, f> Inclusion of <a, f> also creates cycle so skip it and check for next minimum cost edge, i.e. <f, d> The inclusion of <f, d> does not create a cycle, so it is a feasible edge, add it. | U_{V} is empty so the tree generated in step 6 is the minimum spanning tree of given graph. Let w(u, v) represent the weight of edge (u, v) Cost of solution: w(a, b) + w(b, c) + w(c, f) + w(f, d) + w(f, e) = 3 + 1 + 4 + 5 + 2 = 15 |

**Problem: Find the cost of Minimal Spanning Tree of the given graph by using Prim’s Algorithm. **

**Solution:**

- Initialize U
_{V}– list of unvisited vertices – with all vertices in given graph. - Prim’s algorithm adds some arbitrary vertex V
_{x }from U_{V }to the partial solution and removes V_{x}from U_{V}. - N
_{E}– set of all neighbour edges of vertices in partial solution is explored. - The neighbour edge with the minimum cost is added to the partial solution if it does not form a cycle and has not already been added to the partial solution.
- Otherwise, select the next minimum cost edge and add it to the partial solution and remove it from the list of unvisited vertices UV.
- This process is repeated until all vertices are visited, i.e. UV becomes empty.
- For a given graph, initially the set of unvisited vertices U
_{V}= {1, 2, 3, 4, 5}.

Partial solution | Set of neighbor edges N_{E} | Cost of neighbor edges | Updated U_{V} |

Step 1: U_{V} = {1, 2, 3, 4, 5}. Let us start with arbitrary vertex 1. Initial partial solution | <1, 2> <1, 3> | 1 3 | {2, 3, 4, 5} |

Step 2: Edge <1, 2> has a minimum cost, so add it. | <1, 3> <2, 3> <2, 4> | 3 3 4 | {3, 4, 5} |

Step 3: Edge <1, 3> has a minimum cost, so add it. | <2, 3> <2, 4> <3, 4> <3, 5> | 3 4 4 2 | {4, 5} |

Step 4: Edge <3, 5> has a minimum cost, so add it. | <2, 4> <3, 4> <5, 4> | 6 4 5 | {4} |

Step 5: Edge <3, 4> has a minimum cost, so add it. | U_{V} is empty so the tree generated in step 5 is the minimum spanning tree of given graph. Let w(u, v) represent the weight of edge (u, v) Cost of solution: w(1, 2) + w(1, 3) + w(3, 4) + w(3, 5) = 1 + 3 + 4 + 2 = 10 |

## Some Popular Problems Solved by Greddy Algorithm

Greedy algorithms are used to find an optimal or near-optimal solution to many real-life problems. A few of them are listed below :

- Binary Knapsack Problem
- Fractional Knapsack Problem
- Job Scheduling Problem
- Activity Selection Problem
- Huffman Coding
- Optimal Storage on Tapes
- Optimal Merge Pattern
- Prim’s Algorithm
- Kruskal’s Algorithm
- Dijkstra’s Algorithm

Additional Reading: Wiki