Greedy approach is used by Prim’s algorithm to find the minimum cost spanning tree as that of Kruskal’s algorithm. The shortest path first algorithms similarity is shared by Prim’s algorithm.
But in contrast with Kruskal’s algorithm, the nodes are treated as single tree by Prim’s algorithm and new nodes are added to the spanning tree from the graph.
Prims algorithm is better understood with an example -
All the loops and parallel edges are removed from the given graph. In case of parallel edges, keep the one which has the least cost associated and remove all others.
In this case, choose S node as the root node of Prim's spanning tree. Any node can be chosen as a root node. In spanning tree all the nodes of a graph are included and because it is connected then there must be at least one edge, which will join it to the rest of the tree.
After choosing the root node S, see that S,A and S,C are two edges with weight 7 and 8, respectively. Choose the edge S,A as it is lesser than the other.
Now, the tree S-7-A is treated as one node and check for all edges going out from it. Select the one which has the lowest cost and include it in the tree.
After this step, S-7-A-3-C tree is formed. Now again treat it as a node and check all the edges again. However, choose only the least cost edge. In this case, C-3-D is the new edge, which is less than other edges' cost 8, 6, 4, etc.
After adding node D to the spanning tree, two edges are going out of it having the same cost, i.e. D-2-T and D-2-B. Thus, can add either one. But the next step will again yield edge 2 as the least cost. Hence, a spanning tree with both edges included are added.
It is found that the output spanning tree of the same graph using two different algorithms is same.
Data Structure & Algorithms Related Interview Questions
|RDBMS Interview Questions||DBMS Interview Questions|
|Adv Java Interview Questions||Core Java Interview Questions|
|C Interview Questions||Database Administration Interview Questions|
|CSS Advanced Interview Questions||Maven Interview Questions|
|Computer architecture Interview Questions||Object Oriented Analysis and Design Interview Questions|
|Standard Template Library (STL) Interview Questions||Xml Publisher Interview Questions|
Data Structure & Algorithms Tutorial
Data Structure & Algorithms
All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd
Wisdomjobs.com is one of the best job search sites in India.