Prims algorithm

Prim’s is a minimum spanning tree algorithm

Here are the steps to proceed :

First, remove all “looping edge", which means edge starting from a node, to arrive to the same node.

Then, remove parallel edges (edges having common origin, and common destinations).

Select any arbitrary vertex as a source.

1)Select the minimum adjacent edge from the source.

2)Create a list , containing all the nodes included into the tree.

3)We’ll select the minimum adjacent edge to any of the included node. But, we don’t include any edge leading to a node already included in the tree, in order to prevent the apparition of a cycle).

This recursion will finally lead to a minimum spanning tree

We conclude that the obtained tree should have the same number of nodes as the original one , and that all edges included in it , should exclusively come from the initial tree.