Prim’s Algorithm | Prim Algorithm Example

Prim’s Algorithm-

 

  • Like Kruskal’s Algorithm, Prim’s Algorithm is another greedy algorithm used for finding the Minimum Spanning Tree (MST) of a given graph.
  • The graph must be weighted, connected and undirected.

 

Steps for implementing Prim’s Algorithm-

 

Step-01:

 

  • Randomly choose any vertex.
  • We usually select and start with a vertex that connects to the edge having least weight.

 

Step-02:

 

  • Find all the edges that connect the tree to new vertices, then 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.

 

Time Complexity-

 

Worst case time complexity of Prim’s Algorithm

= O(ElogV) using binary heap

= O(E + VlogV) using Fibonacci heap

 

Explanation-

 

  • If adjacency list is used to represent the graph, then using breadth first search, all the vertices can be traversed in O(V + E) time.
  • We traverse all the vertices of graph using breadth first search and use a min heap for storing the vertices not yet included in the MST.
  • To get the minimum weight edge, we use min heap as a priority queue.
  • Min heap operations like extracting minimum element and decreasing key value takes O(logV) time.

 

So, overall time complexity

= O(E + V) x O(logV)

= O((E + V)logV)

= O(ElogV)

 

This time complexity can be improved and reduced to O(E + VlogV) using Fibonacci heap.

 

PRACTICE PROBLEMS BASED ON PRIM’S ALGORITHM-

 

Problem-01:

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

 

 

Solution-

 

For a video solution explaining the solution step by step, watch this video.

 

Step-01:

 

 

Step-02:

 

 

Step-03:

 

 

Step-04:

 

 

Step-05:

 

 

Step-06:

 

 

Since all the vertices have been included in the MST, so we stop.

Weight of the  MST

= Sum of all edge weights

= 10 + 25 + 22 + 12 + 16 + 14

= 99 units

 

Problem-02:

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

 

 

Solution-

 

For a video solution explaining the solution step by step, watch this video.

The Minimum Spanning Tree (MST) obtained by the application of Prim’s Algorithm on given graph is-

 

 

Weight of the  MST

= Sum of all edge weights

= 1 + 4 + 2 + 6 + 3 + 10

= 26 units

 

To gain better understanding of the concepts of Prim’s Algorithm and to solve more problems,

Watch this video

To practice previous years GATE problems based on Prim’s Algorithm,

Watch this video

 

Download the handwritten notes of “Prim’s Algorithm” here-

Get more notes and other study material of Design and Analysis of Algorithms (DAA).

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
Prim's Algorithm | Prim Algorithm Example
Article Name
Prim's Algorithm | Prim Algorithm Example
Description
Like Kruskal's Algorithm, Prim's Algorithm is a greedy algorithm used to find the Minimum Spanning Tree of graph. Time Complexity Analysis of Prim's Algorithm. Prim Algorithm Example.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-