Let’s say we have 8 houses. We want to setup telephone lines between these houses. The edge between the houses represent the cost of setting line between two houses.
Our task is to set up lines in such a way that all the houses are connected and the cost of setting up the whole connection is minimum. Now how do we find that out? We can use Prim’s Algorithm.
Prim’s Algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every node, where the total weight of all the edges in the tree are minimized.
What is Spanning Tree?
A spanning tree of a connected graph G can be defined as a maximal set of edges of G that contains no cycle, or as a minimal set of edges that connect all vertices.
What is Minimum Spanning Tree?
• It is a tree (i.e., it is acyclic).
• It covers all the vertices V – contains |V| — 1 edges.
• The total cost associated with tree edges is the minimum among all possible spanning trees.
• not necessarily unique.
We start from one vertex and keep adding edges with the lowest weight until we we reach our goal.
The steps for implementing Prim’s algorithm are as follows:
1. Initialize the minimum spanning tree with a vertex chosen at random.
2. Find all the edges that connect the tree to new vertices, find the minimum and add it to the tree
3. Keep repeating step 2 until we get a minimum spanning tree
Prim’s Algorithm Applications:
1. Distances between the cities for the minimum route calculation for transportation.
2.For Establishing the network cables these play important role in finding the minimum cables required to cover the whole region
3. Applications in CS Domains:
1.All this path finding algorithms are used in AI (Artificial Intelligence)
Implementation in Python
Implementation in C++
The running time for prim’s algorithm is O(VlogV + ElogV) which is equal to O(ElogV) because every insertion of a node in the solution takes logarithmic time. Here, E is the number of edges and V is the number of vertices/nodes. However, we can improve the running time complexity to O(E + logV) of prim’s algorithm using Fibonacci Heaps.
With this article at Logicmojo, you must have the complete idea of analyzing Prim's Algorithm.
Good Luck & Happy Learning!!