Minimum Spanning Tree
May 27, 2009 Leave a comment
A Minimum Spanning Tree is a tree that includes all the vertices of the graph. (Tree is a graph that is connected and has no cycles.)
So how do we find a MST of a graph? Standard textbook approach would be to use a greedy algorithm.
(Greedy algorithm: An algorithm where thinking greedily helps you to find the solution 🙂 i.e. local optimal solutions lead to a global optimal solution.)
We’ll see three ways to find the MST.All are greedy.
1. Take the entire graph and start deleting edges one by one. Now, we have to be greedy. So, select the heaviest edge that is left in the graph, and delete it. Now, we also have to ensure that the resultant graph spans the graph. So, do not delete any edge that causes the graph to become disconnected; instead check for the next lightest edge to delete.
So, keep deleting edges starting from the heaviest to the lightest keeping in mind the above rules.
Till when do we continue this deletion?? Well, do it till you can delete no more edges without disconnecting the graph. Thats it. We have a MST.
2. Initially MST is empty. Add edges to this to get the MST. How to add edges? Again, greedily. Take the lightest edge. Add it to the MST. Now, we also need to ensure that the resultant MST remains a tree, i.e. there should be no cycles. So, while adding edges, do not add edges that cause the MST to have a cycle. Instead, go to the next heavier edge to add.
So, keep adding edges successively starting from the lightest to the heaviest, keeping in mind the above rules.
When do you stop? Simple; when addition of any more edge to the MST creates a cycle.
3. Initially the MST is empty. And again we’ll add edges greedily. Add the lightest edge to the MST. You get a connected component of 2 vertices, right? Now add the lightest edge that is incident upon this connected component. Ensure that the added edge does not create a cycle in the MST. In case the edge creates a cycle, skip adding it and proceed to the next heavier edge incident upon the connected component.
Keep adding till no more edges can be added without creating a cycle. There’s the MST.