However, we will choose only the least cost edge. Now we'll again treat it as a node and will check all the edges again. We select the one which has the lowest cost and include it in the tree.Īfter this step, S-7-A-3-C tree is formed. Now, the tree S-7-A is treated as one node and we check for all edges going out from it.

We choose the edge S,A as it is lesser than the other. Step 3 - Check outgoing edges and select the one with less costĪfter choosing the root node S, we see that S,A and S,C are two edges with weight 7 and 8, respectively. So the answer is, in the 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. One may wonder why any video can be a root node. This node is arbitrarily chosen, so any node can be the root node. In this case, we choose S node as the root node of Prim's spanning tree. Step 2 - Choose any arbitrary node as root node In case of parallel edges, keep the one which has the least cost associated and remove all others. Remove all loops and parallel edges from the given graph.

To contrast with Kruskal's algorithm and to understand Prim's algorithm better, we shall use the same example − Step 1 - Remove all loops and parallel edges 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. Prim's algorithm shares a similarity with the shortest path first algorithms. Prim's algorithm to find minimum cost spanning tree (as Kruskal's algorithm) uses the greedy approach.

Prim algorithm