Minimum Spanning Tree - Prims's Algorithm

Prim’s algorithm

Prim’s Algorithm also uses the Greedy approach to find the minimum spanning tree. In Prim’s Algorithm we grow the spanning tree from a starting position. Unlike an edge in Kruskal’s Algorithm, we add a vertex to the growing spanning tree in Prim’s Algorithm.

Solution

The algorithm follows the steps listed below:

• Maintain two disjoint sets of vertices: one containing vertices in the growing spanning tree and another that contains vertices not in the growing spanning tree.
• Select the cheapest vertex that is connected to the growing spanning tree and is not in the growing spanning tree and add it into the growing spanning tree. This can be done using

...