Kruskal's Algorithm

Given a weighted graph, many times we are interested in finding a minimum spanning tree (MST) for that graph. Kruskal's algorithm is a greedy method which does just this. A spanning tree is a subset of the edges of a graph that connects to every vertex, but contains no cycles. This spanning tree is called a minimum spanning tree if in addition the sum of the weights of the edges included in this tree is less than or equal to the sum of the weights of the edges of any other spanning tree for this graph.

Kruskal's algorithm works by the following procedure.
1. Initially each vertex is a stand-alone tree, so for each v in V, we define the tree Treev = {v}. The set of selected edges E* is initially empty.
2. Find the edge e = (u, v) of minimum weight such that u and v belong to different trees. If no such edge exists, go to 6.
3. Merge the trees Tlookup(u) and Tlookup(v).
4. Add the edge e to E* and remove the edge e from the graph.
5. If the size of E* is less than n - 1, go to step 2. Else go to step 7.
6. If you reached this step. then the graph is not connected.
7. If you reached this step, then E* is a minimum spanning tree.


Show Work?
your browser does not support the canvas tag