Let G=(V,E) be an undirected,connected and weighted graph.A sub-graph T=(V,E’) of G is a spanning tree of G if T is a

tree.There may be several spanning trees that may be extracted from it.A spanning tree has N vertices and N-1 edges.This is because of the property of trees.A minimum cost spanning tree is a spanning tree which has a minimum total cost.Prims algorithm can be used to obtain the minimum cost spanning tree.

**Example-**

cost[1:N][1:N] is the cost matrix of the graph.If there is no edge from i to j,then cost[i][j]=INT_MAX.If i equals j,then cost[i][j]=0.

Cost matrix for a graph is-

@ denotes INT_MAX

0 6 1 7 @ @

6 0 5 @ 3 @

1 5 0 5 6 4

7 @ 5 0 @ 2

@ 3 6 @ 0 6

@ @ 4 2 6 0

The minimum cost spanning tree consists of the edges-

(1,3) (3,6) (6,4) (3,2) (2,5)

This tree has a minimum cost of 1+4+2+5+3=15.

**Algorithm-**

**Method 1-**

V is the set of vertices.

Let R be the set of edges which are to be extracted to obtain the minimum cost spanning tree.

R=NULL ///Initialize R to null set

Select a minimum cost edge (u,v) from E.

S={u}; //include u in S.

while(S!=V)

{

Let (u,v) be the lowest cost edge such that u is in S and v in V-S;

Add edge (u,v) to set R.

Add v to set S.

}

**Method 2-**

1) Create a set S that keeps track of vertices already included in minimum spanning tree.

2) Assign a key value to all vertices in the input graph. Initialize all key values as INFINITE. Assign key value as 0 for the first vertex so that it is picked first.

3) While S doesnâ€™t include all vertices

{

a) Pick a vertex u which is not there in S and has minimum key value.

b) Include u to S.

c) Update key value of all adjacent vertices of u. To update the key values, iterate through all adjacent vertices. For every adjacent vertex v, if weight of edge u-v is less than the previous key value of v, update the key value as weight of u-v.

u-v edge is in the MST.

}

The time complexity of Prims algorithm is O(N^2).