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[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,
Prim’s Algorithm time complexity

Rewriting the equation,

time complexity of Prim’s Algorithm
  • 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.

Prim’s Algorithm example

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 }.
Partial solutionSet of neighbour edges NECost of neighbour edgesUpdated UV
Step 1 : UV = {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. UV 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.  

Prim’s Algorithm example

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}.
Partial solutionSet of neighbor edges NECost of neighbor edgesUpdated UV
Step 1: UV = {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. UV 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    

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

You may also like...

Leave a Reply

Your email address will not be published.