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 Priority Queues.
• Insert the vertices, that are connected to the growing spanning tree, into the Priority Queue.
• Check for cycles. To do that, mark the nodes which have been already selected and insert only those nodes in the Priority Queue that are not marked as visited.
• In Prim’s Algorithm, we will start with an arbitrary node (it doesn’t matter which one) and mark it.
• In each iteration we will mark a new vertex that is adjacent to the one that we have already marked.
• As a greedy algorithm, Prim’s Algorithm will select the cheapest edge and mark the vertex as visited.

Let us visualize how Prim’s Algorithm works.