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).
