Review

Given an undirected weighted graph, find a set of edges so that all nodes are connected (spanning tree) and the total edge weight is minimized.

Kruskal's algorithm works as follows:

• Sort the list of edges.
• Mark each node with a different color.
• Set up a mapping from color to a list of nodes.
• Initialize the count of nodes in each color to 1.
• Repeat V-1 times:
  • Take the smallest weight edge, discard if both endpoints have the same color.
  • If not, figure out which color has the smaller number of nodes, and recolor them to the color of the other list.