# 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 UV = {V1, V2, V3, . . . , Vn}

1.     Select any arbitrary vertex from input graph G, call that subgraph as partial MST. Remove selected vertex from UV

2.     Form a set NE – a set of unvisited neighbour edges of all vertices present in partial MST

3.     Select an edge e = (u, v) from NE 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 NE. Continue this procedure until we get an edge e which does not form a cycle. Remove corresponding added vertices u and v from UV

4.     Go to step 2 and repeat the procedure until UV 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 ← 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 UV – list of unvisited vertices – with all vertices in given graph.
• Prim’s algorithm adds some arbitrary vertex Vx from UV to the partial solution and removes Vx from UV.
• NE -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 UV.
• This process is repeated until all vertices are visited, i.e. UV becomes empty.
• For given graph, initially the set of unvisited vertices UV = {a, b, c, d, e, f }.

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

Solution:

• Initialize UV – list of unvisited vertices – with all vertices in given graph.
• Prim’s algorithm adds some arbitrary vertex Vx from UV to the partial  solution and removes Vx from UV.
• NE – 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 UV = {1, 2, 3, 4, 5}.

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