What is Prim’s Algorithm and how to solve it?
Prim's Algorithm is the part of Greedy Algorithm in DSA. It selects the edges and forms a tree by the following rules:
- Firstly we have to select the smallest valued edge among all the edges.
- Now see all the edges connected with the selected edge’s vertices and select the least valued one among them.
- Continue the selection of edges till all the vertices comes in connection.
- Select the edges in such a manner that all the edges should be connected and must not form a loop. After the connection of all the vertices count the values written on the edges and their sum will be the minimum cost for that spanning tree. Remember that number of selected edges must be less than the number of vertices present in the graph.
- Time Complexity of prim’s algorithm is of the order of n2 i.e. O(n2).
- Let us take some examples to understand the prim’s algorithm: Example -1: Let’s start with an easy example :
Solution : Step-1: Select the minimum edge (1,6). Step-2: Now there is two edges in front of us (1,2) and (6,5) , as we see (6,5) is smaller that that of (1,2) we select (6,5) and now we have the tree of (1,6,5). Step-3: As we see from all the edges of (1,6,5) the smallest connecting edge is (5,4), so we select this edge and now we have the tree (1,6,5,4). Step-4: Now from all the edges (1,6,5,4) the smallest connected edge is (4,3), so we select this edge and now we have the tree (1,6,5,4,3). Step-5: Now, By this way we select remaining two vertices and now our complete tree becomes (1,6,5,4,3,2,7). Step-6: Count the value of edges i.e. 10+25+22+12+16+14 = 99. So the minimum cost of the spanning tree is 99. Our final tree looks like -
Example-2 : This example will clear all the concepts of prim’s algorithms :
Solution : Step-1: Select the minimum edge , but there are two edges which have minimum value i.e. (A,D) and (C,E) so don't get panic we can select anyone from these two edges, answer will be same. So let we proceed with (A,D). Step-2: Now, select the minimum one connected to this edge i.e. (D,F) and now we have the tree (A,D,F). Step-3: Now, select the minimum valued edge attched among the vertices(A D F ) i.e (A,B) and now we have the the tree (B,A,D,F). Step-4: Now, select the minimum valued edge attched among the vertices(A D F B ) i.e. (B,E) and now we have the tree (E,B,A,D,F). Step-5: Now, select the minimum valued edge attched among the vertices(A D F B E ) i.e. (E,C) and now we have the tree (C,E,B,A,D,F). Step-6: Now, select the minimum valued edge attched among the vertices(A D F B E C ) but now there is a problem occurs that what should we select as there are two same and minimum valued edges (B,C) and (E,F) but we can't select any of them because according to the rule, no loop is allowed in the tree so we proceed with the edge (E,G) and we have the final tree (C,E,G,B,A,D,F). Step-7: Now count all the values of the edges i.e. 5+6+7+7+5+9= 39 . So the minimum cost of the spanning tree is 39. Our Final tree looks like :
- Now please try example 2 by yourself with starting edge (C,E) and comment the answer.
- Now you can solve any of the problems based on the prim’s Algorithm for minimum cost spanning tree.
@Arpit Jain…..Doing good job bro….