Tired of studying the same 2 algorithms (Prism and Kruskal) for developing a Minimum Spanning Tree..? Here you can try a new algorithm developed by a computer science student. Pretty straight forward and simple.

The algorithm presented here uses greedy approach to the problem, since at every stage, it makes a choice that looks best at the moment. That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution. Although greedy algorithms do not always yield an optimal solutions, but for many problems, like the spanning tree problem, they do yield an optimal solution.

Simply put, here a minimum spanning tree is formed in just 4 steps :

The video will make it more clear :

A more formal definition of the algorithm has been presented below. Here the forest ‘S’ grows gradually by the addition of the edged which finally results in a Minimum Spanning Tree.

MBA (G,w)
1. S is initialized to Null
2. For each vertex v belongs to  V[G]
3. Maintain a minimum priority queue, Qv
4. For each vertex v belongs to V[G]
5. u = Extract-Min (Qv)
6. Make-Set (v)
7. If (u,v) does not belongs to S
8. S = S U {(u,v)}
9. For each edge (u,v), (u,v) belongs to E[G]
10. If Find-Set (u) = Find-Set (v)
11. w(u,v) = infinity
12. For each vertex v belongs to V[G]
13. u = Extract-Min (Qv)
14. Make-Set (v)
15. If (u,v) does not belongs to S
16. S = S U {(u,v)}
17. If Find-Set (u) = Find-Set (v)
18. S = S – max ({x,y}), x,y ? Set (u)
19. Return S.

The powerpoint presentation can be downloaded from here : Minimum Spanning Tree