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.

### Like this:

Like Loading...

*Related*

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