Kruskal’s algorithm takes the opposite approach from Prim’s: instead of growing one connected tree, it looks at all edges at once, considers them cheapest-first, and keeps an edge only if it doesn’t create a cycle.

The result is a minimum spanning tree assembled from individually “safe” edges — like buying the cheapest roads that never make a redundant loop.

Its secret weapon is Union-Find, which answers “do these two vertices already connect?” in near-constant time.

How It Works

1. Sort edges by weight ascending.
2. Initialize Union-Find: every vertex is its own component.
3. Process edges: for each (u, v, w) in sorted order:
   • If find(u) ≠ find(v) — they’re in different components. Add the edge and union them.
   • Otherwise, the edge would form a cycle — skip it.
4. Stop early: once V−1 edges are in the MST, it’s complete.

Key Insight

Kruskal takes a global view — it never commits to a starting vertex and never grows a connected region. An edge is accepted only when it merges two previously separate components; an edge within one component would be a cycle.

This is the cut property again, applied edge-by-edge: each accepted edge is the cheapest edge crossing the cut between the two components it joins.

Union-Find turns “do these two connect?” into an almost O(1) check (inverse-Ackermann), leaving sorting as the dominant O(E log E) cost.

Worked Example

Run Kruskal’s on the visualizer’s MST graph. Sorted edges:

C–D(1), A–C(2), D–E(2), D–B(3), C–F(3), A–B(4), D–F(4), B–E(5), A–D(6), E–F(6).

• C–D(1) → different components → add. Components: {C,D}, {A}, {B}, {E}, {F}.
• A–C(2) → add. {A,C,D}.
• D–E(2) → add. {A,C,D,E}.
• D–B(3) → add. {A,B,C,D,E}.
• C–F(3) → add. {A,B,C,D,E,F} — V−1 = 5 edges, stop.

MST edges: C–D, A–C, D–E, D–B, C–F, total weight 1+2+2+3+3 = 11 — the same tree and weight Prim’s produced. In the visualizer, watch edges get accepted (colored) or rejected (marked) in sorted order.

Edge Cases & Pitfalls

• Cycle rejection is mandatory — skipping cycle edges is what makes Kruskal correct: never accept an edge within one component.
• Disconnected graph — the MST won’t cover all vertices; V−1 accepted edges never happens. Detect by counting unions.
• Equal weights — multiple MSTs exist; tie order decides which one you get.
• Directed graphs — MST is undirected: Kruskal assumes undirected edges.
• Sorting dominates — for dense graphs the sort is wasteful vs Prim’s O(V²). Kruskal shines on sparse graphs.

Comparison: Kruskal vs Prim

Applications

• Network design — minimal total cable/pipeline length
• Single-linkage clustering — MST-based groupings
• Image segmentation — graph-based segmentation via MST cuts
• Taxonomy construction — hierarchical classifications

Practice Trajectory

1. Hand-run Kruskal’s on the visualizer graph and confirm the MST weight equals Prim’s.
2. Explain exactly how Union-Find detects a cycle in (u, v).
3. Identify which edges get rejected and why.
4. Argue why Kruskal favors sparse graphs and Prim favors dense ones.
5. Implement Kruskal’s with Union-Find and verify you never accept a cycle edge.