PRIM'S ALGORITHM
Introduction
Given a weighted graph, we need to connect the nodes in the smallest possible way such that there will be a path between every pair nodes. This algorithm is one of the solution for the minimum spanning tree(MST) problem.
It has direct applications to the design of all kinds of networks such communication, computer, transportation, electrical etc. by providing the cheapest way to achieve connectivity.
Working Procedure
- Let MST_V[] store the vertices and let E[] store the edges that are included in MST.
- Initially MST_V[0]=0(first vertex that shall be the source).
- Loop from i =1 to V-1 (V is the no. of vertices).
- Find a minimum weighted edge e=(v,u) among all the edges such that vertex v is in MST_V[] and vertex u is not in MST_V[].
- Then add this edge e to E[] and vertex u to MST_V[].
Time Complexity: O(E * logV)
Code file
Please open this in your pc or with a compatible app in your mobile.
C++ Implementation for PRIM'S ALGORITHMThat's it from this blog post. If you liked it then do share this blog with your friends or people who wanna get into programming world. Thank You!