Prim's algorithm for computing minimal spanning tree

1. Prim’s Algorithm is a famous greedy algorithm.
2. It is used for finding the Minimum Spanning Tree (MST) of a given graph.
3. To apply Prim’s algorithm, the given graph must be weighted, connected and undirected.
   

Prim’s Algorithm Implementation-
 
The implementation of Prim’s Algorithm is explained in the following steps-
 

Step-01:

•  Randomly choose any vertex.
• The vertex connecting to the edge having least weight is usually selected.

 
Step-02:
 

• Find all the edges that connect the tree to new vertices.
• Find the least weight edge among those edges and include it in the existing tree.
• If including that edge creates a cycle, then reject that edge and look for the next least weight edge.
  

Step-03:

 Keep repeating step-02 until all the vertices are included and Minimum Spanning Tree (MST) is obtained.

Prim’s Algorithm Time Complexity-

Worst case time complexity of Prim’s Algorithm is-

1. O(ElogV) using binary heap
2. O(E + VlogV) using Fibonacci heap

Example: Construct the minimum spanning tree (MST) for the given graph using Prim’s Algorithm-

Step-1: 

1. Randomly choose any vertex. ( Here vertex 1)
2. The vertex connecting to the edge having least weight is usually selected.
   

Step-2: Now we are at node / Vertex 6, It has two adjacent edges, one is already selected, select second one.

Step-3: Now we are at node 5, it has three edges connected, one is already selected, from reaming two select minimum cost edge (that is having minimum weight) Such that no loops can be formed by adding that vertex

Step-4: Now we are at node 4, select the minimum cost edge from the edges connected to this node. Such that no loops can be formed by adding that vertex.

Step-5: Now we are at node 3, since the minimum cost edge is already selected, so to reach node 2 we selected the edge which cost 16. Then the MST is 

Step-6: Now we are at node 2, select minimum cost edge from the edges attached to this node. Such that no loops can be formed by adding that vertex.

Since all the vertices have been included in the MST, so we stop.
 
Now, Cost of Minimum Spanning Tree
= Sum of all edge weights
= 10 + 25 + 22 + 12 + 16 + 14
= 99 units