Prim’s Algorithm
In this blog we will discuss about what is Prim’s algorithm.
Before we jump onto prims algorithm let’s take a quick recap of what is spanning tree and minimum spanning tree.
Spanning tree
A spanning tree is a subset of Graph G, which takes care of all the vertices with least convincible number of edges. Hence, a spanning tree doesn’t have cycles and it can’t be withdrawn. All the edges should be associated otherwise it will not be considered as a spanning tree. A disconnected diagram can’t have any spanning tree.
General Properties of Spanning tree:
i) A graph may have more than 1 spanning tree.
ii) There are no loops in a spanning tree.
iii) Removing one edge from the spanning tree will make it minimally connected.
iv) Adding an extra edge to the spanning tree will result in formation of a loop and it will make it maximally connected.
Mathematical Properties:
i) No of edges is 1 less than the no of vertices in a spanning tree.
ii) From a complete graph, by removing maximum e-n+1 edges, we can construct a spanning tree.
iii) A graph G can have maximum n^(n-2) number of spanning trees.
Minimum Spanning Tree
In a weighted graph, a spanning tree is a traversing tree that has least weight than any remaining spanning trees of that similar diagram. In real-life circumstances, this weight can be estimated as distance, blockage/clog, traffic load or any inconsistent worth indicated to the edges.
Minimum Spanning-Tree Algorithm:
There are two important spanning tree algorithms:
i) Kruskal’s Algorithm
ii) Prim’s Algorithm
Both are greedy algorithms.
Prim’s Algorithm:
Prim’s Algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected diagram. This implies it observes a subset of the edges that shapes a tree that incorporates each vertex, where the total weight of all the edges in the tree is limited. The algorithm works by building this tree each vertex in turn, from an arbitrary beginning vertex, at each progression adding the cheapest conceivable connection from the tree to another vertex.
Algorithm:
Step 1: Pick any node and mark MST as 0 for that node, and then mark all other nodes/vertices as infinity and mark them as min heap.
Step 2: Extract min node u from min heap.
Step 3: For all edges update the cost of vertices, if the now marked node is
Step 4: if heap is not vacant then heapify and go to Step 2.
Example:
Consider the graph given below. We will see the step-by-step procedure of the algorithm, how it actually works.
Step 1:
Now, we will consider all the vertices first. Then we will choose the distance/edge with least weight. The algorithm proceeds by selecting edges with minimum weight.
Step 2:
We will connect the first pair of nodes with minimum distance.
Step 3:
After we reached the node 6, we will follow on the line and connect node 6 and node 5.
Step 4:
After we reach node 5, we can observe that there are two edges bulging out of the node. So we will choose the edge with minimum distance and hence connect node 5 and node 4 in this step.
Step 5:
After reaching node 4, we again need to pick the edge with minimum distance and hence join node 3 and node 4.
Step 6:
After reaching node 3 we need to connect node 2 for continuing the follow on line.
Step 7:
After reaching 2, we can’t connect node 1 as it will form a cycle(loop), so we will connect node 2 and node 7 at this step and we get our minimum weight using Prim’s Algorithm.
Prim’s Algorithm Application:
General Applications:
i) Distances between the cities for the minimum route calculation for transportation.
ii) For Establishing the network cables, prim’s algorithm play important role in finding the minimum cables required to cover the whole region.
Applications in CS Domains:
i) All this path finding algorithms are used in AI (Artificial Intelligence)
ii) Game Development
Hope you found this blog informative.
Thank you.