Minimum Spanning Trees: Kruskal's Algorithm
What you'll learn: How to build a minimum spanning tree by greedily selecting the lightest edges that don't create cycles.
The Core Idea
You already know what a spanning tree is—a subgraph that connects all vertices using the minimum number of edges (no cycles, all vertices reachable). When edges have weights (costs, distances, etc.), a minimum spanning tree (MST) is the spanning tree with the smallest total weight.
Kruskal's algorithm finds an MST using a simple greedy strategy:
- Sort all edges by weight, from lightest to heaviest
- Examine edges in order, one at a time
- Add an edge to your growing forest if and only if it doesn't form a cycle with edges already chosen
- Stop when you have n - 1 edges (for n vertices)—you've built a tree!
Why It Works
The greedy choice is safe: at each step, taking the lightest available edge that doesn't create a cycle guarantees you won't miss the optimal solution. The algorithm builds up a forest (a collection of trees) that gradually merges into a single tree spanning all vertices.
Analogy
Imagine building a road network connecting cities as cheaply as possible. You always pick the cheapest road option that connects previously unconnected groups of cities. You never build a road that creates a loop (wasteful redundancy). Eventually, all cities connect via the cheapest possible network.
Checking for Cycles
The key implementation detail: how do you detect if adding an edge creates a cycle? Use a union-find (disjoint-set) data structure to efficiently track which connected components each vertex belongs to.
Key Takeaway: Kruskal's algorithm builds a minimum spanning tree by sorting edges by weight and greedily adding the lightest edge that connects two different components, ensuring no cycles form.