7.6 KruskalMST

KruskalMST(graph G)

1. Sort the edges of G by increasing weight
2. 1. initialize union-find system on the vertices of G
   2. For each edge (u,v) in order do
      • if the ends of the edge are in different union-find sets
        1. union the two sets
        2. include (u,v) in the MST

This is correct because each edge used is lightest in a cut.

Runtime is O(e lg(n)) where e is the number of edges, n the number of vertices.

[ Union-find discussion not yet in the notes. Includes lg*() function discussion. ]