Minimum spanning tree
A spanning tree of a connected weighted graph connects all vertices using a subset of edges with no cycle. The minimum spanning tree or MST is the spanning tree whose total edge weight is the smallest possible. MSTs model the cheapest way to wire a network so everything stays connected.
Kruskal's greedy rule
Kruskal's algorithm builds the MST by considering edges from cheapest to most expensive.
- Sort all edges by weight, ascending.
- Walk through them and add an edge only if it connects two vertices that are not already in the same group.
- Skip an edge if both endpoints are already connected, since adding it would form a cycle.
- Stop once the tree has one fewer edge than the vertex count.
Union find keeps it fast
To test whether two endpoints are already connected, Kruskal uses a union find or disjoint set structure. It answers find queries and merges groups in almost constant time. The dominant cost is sorting the edges. The greedy choice is safe because the lightest edge crossing any partition of vertices is always part of some MST, a fact known as the cut property.
Key idea
Kruskal sorts edges and greedily adds the cheapest one that joins two separate groups, using union find to reject cycle forming edges.