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.
