--- title: "Union-Find and Minimum Spanning Trees" description: "Kruskal's method processes edges in increasing weight and joins separate components. Union-find tracks those components with rooted parent trees. Union by size together with path compression gives alm" 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-11-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 processes edges in increasing weight and joins separate components. Union-find tracks those components with rooted parent trees. Union by size together with path compression gives almost constant amortised time per operation. 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 We use finite, connected, undirected graphs. A tree is connected and has no cycles: exactly one simple path joins each pair of vertices. A simple path does not repeat a vertex. A spanning tree includes every vertex and uses only edges of the original graph. Having the expected number of edges alone does not prove that a graph is a tree; it must also be connected. A tree with n vertices has n - 1 edges. Start with n separate vertices. Each edge joining different components reduces the component count by one. Reaching one component takes n - 1 joins. A spanning tree therefore keeps n - 1 edges. From an original graph with m edges, it deletes m - (n - 1) edges while preserving connectivity. Kruskal finds a spanning tree with minimum total edge weight. Sort edges from lightest to heaviest. Accept an edge only if its endpoints are in different components; otherwise it would create a cycle. Merge the components after accepting it. Equal-weight edges may be considered in either order. Stop after n - 1 accepted edges, or scan the rest and reject them. Add only accepted weights to find the tree's total. **Example.** For vertices P, Q, R, S, the edges are PQ 2, RS 3, PR 4, QR 6 and QS 8. Accept PQ, then RS, then PR. The first two edges need not touch. PR joins their components. All vertices are now connected, with total weight 2 + 3 + 4 = 9. If scanning continues, QR and QS are rejected because each would create a cycle. Union-find stores each set as a rooted parent tree. Initially each vertex is its own root. find follows parents to the root. Equal roots mean equal sets. union links different roots; if the roots match, nothing changes. During Kruskal, these sets track accepted-edge components, not all input edges. Equal roots mean a new edge would create a cycle. Parent links are bookkeeping links and need not be input edges. Different roots do not rule out an input-graph path. Full path compression makes every visited non-root vertex point directly to the root. Suppose V points to U, U to R, and R to root P. After find(V), V and U point to P; R already did. Vertices outside the visited path keep their parents. Compression changes neither the root nor set membership. A later find(V) follows one parent link. Union by size links the smaller set's root under the larger set's root. Ties allow either root. Each depth increase at least doubles a vertex's set size, so find takes O(log n) worst-case time. Adding path compression gives O(alpha(n)) amortised time per find or union, where alpha is the slowly growing inverse Ackermann function. The bound applies across a sequence; it does not promise constant time for each call. A cut divides all vertices into two nonempty groups. Suppose accepted forest F is contained in some minimum spanning tree (MST), and no edge of F crosses the cut. A lightest crossing edge E is safe: some MST contains both F and E. Kruskal uses one current component as a group. Its next accepted edge is lightest across that cut. With ties, 'lightest' can describe several edges; different choices can produce different MSTs. Use an exchange argument. Take an MST T containing F. If T lacks E, adding E creates one cycle. Another edge H on that cycle crosses the cut. H is not in F, since no edge of F crosses. Remove H from the cycle. The result is a spanning tree keeping F and E. E weighs no more than H, so the total cannot rise. The resulting tree is also minimum. **Recap.** Kruskal joins separate components in weight order. Union-find tracks them. Size and compression reduce costs; a cut-respecting exchange preserves an MST containing the accepted edges. *Original teaching text, questions, worked solutions and flashcards written for this dataset. Graph-theory source records were consulted for mathematical facts and assessment design; their prose and exercises were not copied.* ## Practice 14 questions on this page, each with its working shown. ## Needs first - [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) ## Optional connections - [Amortised Analysis](https://lightmysky.com/learn/computing/amortised-analysis-mt_1zLrl5RKGr)