Union-Find and Minimum Spanning Trees
Kruskal's method sorts the edges and adds any that joins two separate pieces, which needs a structure that answers whether two vertices are already connected. Union-find answers it in almost constant time using a forest with path compression.
What a learner can do afterwards
- Run Kruskal's method on a small weighted graph and say why each rejected edge was rejected
- Perform union and find operations and show what path compression changes
- Explain why the cut property makes the greedy edge choice safe
1 · Read
A tree is a connected graph with no loops: one route between any two towns and no wasted roads. A spanning tree touches every vertex while using only edges from the graph. A connected graph with n vertices always has a spanning tree with exactly n minus 1 edges, so building one means deleting edges until no loops remain while keeping everything reachable.
Kruskal builds the cheapest such tree, called the minimum spanning tree. Sort the edges from lightest to heaviest and take each edge that joins two towns not already connected, skipping any edge that would close a loop. On vertices A, B, C, D with weights AB 1, CD 2, AC 3, BC 4, BD 5, you add AB, CD, and AC, then reject BC since all four towns are already one piece.
Union find answers the are they connected question in almost constant time. It keeps the vertices in a forest of small trees: union merges two trees when an edge joins them, and find walks up to the root. Path compression flattens as it works: calling find on E through D to B to root A rewires D and E to point straight at A, so later finds on that chain are shorter.
The cut property is why the greedy choice is safe. Imagine a cut splitting the vertices into two groups: the lightest edge crossing that cut belongs to some minimum spanning tree, so adding it can never hurt. After a union, find on either node returns the same root, which confirms the merge worked.
Sort edges light first, join separate pieces, compress paths, and trust the lightest edge across every cut.
2 · Watch
Take it off screen
Where it sits
This opens up
Nothing builds on it yet.
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.