Prim's Method

DEFINITION - Minimum Cost Spanning Tree

Let G=(V,E,W) be any weighted graph. Then a spanning tree whose cost is minimum is called minimum spanning tree. The cost of the spanning tree is defined as the sum of the costs of the edges in that tree.

Prim's Algorithm 

In Prim’s algorithm, greedy criterion is used to determine the next edge that have minimum cost. It has a time complexity of O(n²). The steps to find minimum cost spanning tree using Prim’s algorithm is

The steps involved are

Step 1: Select the minimum cost edge and include in minimum spanning tree T

Step 2: Select adjacent edges to T which is minimum in cost and add to T

Step 3: Repeat Step 1 and 2 for n-1 edges and no cycle

EXAMPLE