Mathematics
Kruskal's Algorithm for Building Minimum Spanning Trees
Quick fact
Kruskal's algorithm can always find the minimum spanning tree of any connected, weighted graph, and it does so by simply sorting edges by weight and adding the smallest safe edge, guaranteeing an optimal solution.
Why this is interesting
How can you connect all the cities in a region with the least total length of road, without building any loops? The answer uses a surprisingly simple rule: always pick the cheapest road that doesn't create a cycle.
Read the full explanation
Understanding Kruskal's Algorithm for Building Minimum Spanning Trees
Think of a graph as a set of towns (nodes) and possible roads (edges) with building costs (weights). A spanning tree is a set of roads that connects every town with exactly one path between any two towns—no cycles, like a tree branching out. The minimum spanning tree is the cheapest such set. Kruskal's algorithm builds it in three steps: first, list all roads from cheapest to most expensive. Second, go through this list and add each road to your tree if it doesn't create a loop. Third, repeat until you have connected all towns (which happens after you've added enough roads). The key insight is that you're always choosing the cheapest next road that keeps the tree acyclic, and because you've sorted the edges, you never need to reconsider a choice.
A deeper explanation
The algorithm works because of a fundamental property of minimum spanning trees called the cut property. It states that the smallest edge crossing a cut (a partition of vertices into two groups) must belong to some minimum spanning tree. When you add an edge, you're effectively making a cut that separates the vertices already connected by your tree from the rest. The edge you pick is the smallest that crosses that cut, so it's safe to include. By repeatedly applying this, the greedy approach ensures optimality. To efficiently detect cycles, you can use a union-find data structure, which tracks which vertices are in the same component. For each edge, you check if its endpoints are in the same set; if not, you merge them. This makes the algorithm run in O(E log E) time, dominated by sorting the edges. Kruskal's algorithm is thus a perfect example of a greedy algorithm that is proven to be correct.