--- title: "Union-Find and Minimum Spanning Trees" description: "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 " canonical: https://lightmysky.com/learn/computing/union-find-and-minimum-spanning-trees-mt_zOJei4yCtr source: https://lightmysky.com/learn/computing/union-find-and-minimum-spanning-trees-mt_zOJei4yCtr.md retrieved: 2026-09-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # 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. Subject: Computing · Area: Algorithms & Data Structures · Ages 20 to 21 Page: https://lightmysky.com/learn/computing/union-find-and-minimum-spanning-trees-mt_zOJei4yCtr ## Ready when they can - 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 ## Lesson: The cheapest way to connect everything 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. **Example.** 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. **Tip.** 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. **Recap.** Sort edges light first, join separate pieces, compress paths, and trust the lightest edge across every cut. ## Practice 14 questions on this page, each with its working shown. ## Needs first - [Amortised Analysis](https://lightmysky.com/learn/computing/amortised-analysis-mt_1zLrl5RKGr) - [Greedy Choice and the Exchange Argument](https://lightmysky.com/learn/computing/greedy-choice-and-the-exchange-argument-mt_9Fj28VDAV-) - [Graphs and How to Store Them](https://lightmysky.com/learn/computing/graphs-and-how-to-store-them-mt_tSO-F1sTuu)