# 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 -

### Step 1 - Remove all loops and parallel edges

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.

### 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.

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.