Data Structure & Algorithms - Data Structure & Algorithms Spanning Tree - Prim's Spanning Tree Algorithm - Data Structure & Algorithms

What is Prim’s Spanning Tree Algorithm?

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 -

MST Graph

Step 1 - Remove all loops and parallel edges

MST with Loops

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.

MST without Loops

Step 2 - Choose any arbitrary node as root node

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.

Step 3 - Check outgoing edges and select the one with less cost

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.

MST Graph Step 1

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.

MST Graph Step 2

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.

MST Graph Step 3

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.

MST Prim's Algorithm

It is found that the output spanning tree of the same graph using two different algorithms is same.


All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Data Structure & Algorithms Topics