Kruskal's algorithm and union–find

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Cycle property? from Lesson 6.2.1
• Sorting E items costs? from Lesson 3.3.1
• Height of a binary heap with n nodes? from Lesson 0.2.2

1 · The Hook

🎣

Kruskal's algorithm is the simplest greedy algorithm in Phase 6: sort the edges by weight and accept each one unless it would close a cycle. The only hard part is the test "would this edge close a cycle?", answered by a tiny data structure called union–find.

2 · Predict First

🤔

Kruskal on the six-town graph: the edges in weight order are B–C 1, A–C 2, D–E 2, E–F 3, A–B 4, B–D 5, … Which of the first six is rejected?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

A–B 4: by then B–C and A–C already join A, B and C, so A–B would close a cycle.

Kruskal's algorithm

sort edges by weight
each vertex is its own set
for each edge (u, v) in order:
    if find(u) != find(v):          // different trees: no cycle
        add (u, v) to the MST; union(u, v)
    stop after V - 1 edges

Each accepted edge is the lightest edge crossing the cut between its tree and the rest, so the cut property makes it safe.

Union–find (disjoint sets)

• Each set is a tree; find(x) follows parent pointers to the root.
• Union by rank (or size): hang the shorter tree under the taller; tree height stays ≤ log₂ n.
• Path compression: during find, point every visited node straight at the root.
• With both, a sequence of m operations costs O(m·α(n)), where α grows so slowly it is ≤ 4 in practice.

Cost

Sorting dominates: O(E log E) = O(E log V) (since E ≤ V², log E ≤ 2 log V). The union–find work is nearly linear.

Six-town trace

MST weight 13. Kruskal builds a forest that merges into one tree.

4 · Visual

Union-find for the trace (root shown first)

start          {A} {B} {C} {D} {E} {F}
B-C accept     {B,C} {A} {D} {E} {F}
A-C accept     {A,B,C} {D} {E} {F}
D-E accept     {A,B,C} {D,E} {F}
E-F accept     {A,B,C} {D,E,F}
A-B reject     find(A) = find(B)
B-D accept     {A,B,C,D,E,F}   done

5 · Worked Examples

Example 1 Easy

In the six-town trace, how many edges are examined before the MST is complete?

Solution

B–C, A–C, D–E, E–F, A–B (rejected), B–D: 6.

Example 2 Medium

The CLRS textbook graph (vertices a–i) has edges a–b 4, a–h 8, b–c 8, b–h 11, c–d 7, c–f 4, c–i 2, d–e 9, d–f 14, e–f 10, f–g 2, g–h 1, g–i 6, h–i 7. MST weight?

Solution

Kruskal accepts g–h 1, c–i 2, f–g 2, a–b 4, c–f 4, c–d 7, one of the 8s, d–e 9: 37.

Example 3 GATE

For the CLRS graph above, how many distinct MSTs are there?

Solution

a–h and b–c (both 8) are interchangeable: 2.

6 · GATE Traps

⚠️

• Kruskal is dominated by sorting: O(E log E) = O(E log V).
• Before the end Kruskal's chosen edges form a forest, not one tree (contrast Prim).
• Ties can be broken either way, possibly giving different MSTs of the same weight.
• Union by rank alone gives O(log n) finds; with path compression, nearly O(1) amortised.

7 · Memory Hook

🧠

"Sort the edges; take each one that joins two different trees."

8 · Connect the Dots

Kruskal grows a forest edge by edge. Prim's algorithm, next, grows one tree from a start vertex, much like Dijkstra will later.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT2 marksKruskal

MST weight of the CLRS graph in the Medium example?

Numerical answer: ________

Q2NAT1 markKruskal steps

In the six-town Kruskal trace, how many edges are rejected?

Numerical answer: ________

Q3MCQ1 markKruskal cost

Kruskal's algorithm with union–find runs in:

• (A) O(E log E)
• (B) O(VE)
• (C) O(V²)
• (D) O(E + V)

Q4NAT1 markLast edge

In the CLRS graph, what is the weight of the last edge Kruskal adds?

Numerical answer: ________

Q5MSQ2 marksUnion–find

Which are true?

• (A) Union–find requires the edges to be sorted.
• (B) With union by rank, every tree has height at most log₂ n.
• (C) Path compression makes find point visited nodes at the root.
• (D) Kruskal rejects edge (u, v) when find(u) = find(v).

10 · Rule Card

• Kruskal: sort edges; add (u, v) if find(u) ≠ find(v); stop at V − 1 edges.
• O(E log E) = O(E log V); the partial result is a forest.
• Union by rank: height ≤ log n; plus path compression: ~O(α(n)) per operation.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

Kruskal's algorithmunion–find (disjoint sets)find and unionunion by rankpath compressioninverse Ackermann αKruskal cost O(E log E)

12 · Answer Vault