general algorithm for prim’s minimum spanning tree


Prim’s algorithm (in general terms) for minimum spanning tree
*************************************************************

1.Let T be the set of edges in the minimum spanning tree.

2.Initialize T=Ø.

3.Let TV be the set of vertices in the tree.

4.Initialize TV={1}.

5.Let E be the set of graph edges.

6.Repeat through steps 7,8,9,10 while E≠Ø and |T|≠n-1.

7.Let(u,v)be the least cost edge such that u is in TV and v is not in TV.

8.if There is no such edge go to step 11.

9.E=E-{(u,v)} i.e. delete the edge from E.

10.Add the edge (u,v) to T.

11.If(|T|=n-1) T is a minimum cost spanning tree else the network is not

   connected and has no spanning tree.

One thought on “general algorithm for prim’s minimum spanning tree”

  1. Pingback: buy cialis online

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s