Prim’s algorithm for finding MST

Prim’s algorithm for finding MST (Minimum Spanning Tree)

Prim's algorithm to find minimum cost spanning tree uses the greedy approach. Prim's algorithm, in contrast with Kruskal's algorithm, treats the nodes as a single tree and keeps on adding new nodes to the spanning tree from the given graph.

Example:

Step 1 - Remove all loops and parallel edges. 

In case of parallel edges, keep the one which has the least cost associated and remove all others.

Step 2 - Choose any arbitrary node as root node

In this case, we choose S node as the root node of Prim's spanning tree. This node is arbitrarily chosen, so any node can be the root node. 

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

After choosing the root node S, we see that S,A and S,C are two edges with weight 7 and 8, respectively. We choose the edge S,A as it is lesser than the other.

We check for all edges going out from (S,A). We select the one which has the lowest cost and include it in the tree.

This process is repeated until all the nodes in the graph are covered.

Example 2: