Prims Algorithm

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

Leave a Reply

Your email address will not be published. Required fields are marked *

*

* Copy This Password *

* Type Or Paste Password Here *

42,383 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>