Kruskal's Algorithm: Building Minimum Spanning Trees with Union-Find

4 min read

Today I learned about Kruskal’s algorithm while solving Advent of Code 2025 Day 8. Sort the edges, add the short ones, skip anything that closes a cycle. That’s the whole thing, and it’s optimal. Pairing it with Union-Find for the cycle check is what makes it fast enough to run.

The Problem

Given junction boxes suspended in 3D space, connect them with the minimum total wire length such that electricity can flow between all boxes. For example, given these 5 boxes:

A(0,0,0), B(1,0,0), C(2,0,0), D(0,1,0), E(10,10,10)

We could connect all boxes in many ways, but the minimum spanning tree (MST) minimises total wire used while keeping everything connected.

What is Kruskal’s Algorithm?

Kruskal’s algorithm is a greedy algorithm that builds a minimum spanning tree by:

  1. Sorting all possible edges by weight (distance)
  2. Processing edges from shortest to longest
  3. Adding each edge to the tree only if it connects two separate components (doesn’t create a cycle)

Greedily choosing the shortest edge that doesn’t create a cycle always lands on an optimal MST, because adding a longer edge when a shorter one could do the job can never improve the solution.

Implementation in Rust

Here’s the core algorithm using Union-Find to track connected components:

// Sort all edges by distance
edges.sort_by(|a, b| a.distance.partial_cmp(&b.distance).unwrap());

// Process edges in order, connecting disjoint components
let mut uf = UnionFind::new(data.len());

for edge in edges {
    if uf.union(edge.from, edge.to) {
        // Edge added - components were separate
        if uf.component_count() == 1 {
            // MST complete - all nodes connected
            break;
        }
    }
    // else: Edge skipped - would create cycle
}

The Union-Find structure handles the critical question: “Are these two nodes already in the same component?” in near-constant time.

Walkthrough: Building an MST

Let’s trace through connecting 4 boxes (A, B, C, D):

Initial state: {A}, {B}, {C}, {D} (4 components)

Edges sorted by distance:
1. A-B: 1.0
2. B-C: 1.0
3. A-D: 1.0
4. C-D: 1.4
5. B-D: 1.4
6. A-C: 2.0

Step 1: Process A-B (distance 1.0)
  Union(A, B) → Success
  Components: {A,B}, {C}, {D} (3 components)
  ✓ Edge added to MST

Step 2: Process B-C (distance 1.0)
  Union(B, C) → Success (connects {A,B} with {C})
  Components: {A,B,C}, {D} (2 components)
  ✓ Edge added to MST

Step 3: Process A-D (distance 1.0)
  Union(A, D) → Success
  Components: {A,B,C,D} (1 component)
  ✓ Edge added to MST
  → MST complete! (N-1 = 3 edges for N=4 nodes)

Step 4: Process C-D (distance 1.4)
  Union(C, D) → Failure (already connected via A-B-C-D path)
  ✗ Edge skipped (would create cycle)

The MST has edges A-B, B-C, A-D with total weight 3.0. The C-D edge was skipped because it would create a cycle.

The Union-Find Part

Everything hinges on answering “are these two nodes already connected?” quickly. Union-Find is what makes that cheap.

fn find(&mut self, x: usize) -> usize {
    if self.parent[x] != x {
        self.parent[x] = self.find(self.parent[x]); // Path compression
    }
    self.parent[x]
}

fn union(&mut self, x: usize, y: usize) -> bool {
    let root_x = self.find(x);
    let root_y = self.find(y);

    if root_x == root_y {
        return false; // Already in same component - would create cycle
    }

    // Connect the components
    self.parent[root_y] = root_x;
    self.component_count -= 1;
    true
}

With path compression, each union() operation is effectively O(α(N)) ≈ O(1) where α is the inverse Ackermann function (grows incredibly slowly—practically constant for any real-world N).

Why Greedy Works Here

If we’ve processed all edges shorter than e, and e connects two separate components, we must add it. Any MST that doesn’t include e would need a longer edge to connect those components later, making it suboptimal.

Greedy fails on plenty of other graph problems. Shortest path needs Dijkstra’s: grabbing the shortest edge at each step doesn’t guarantee the optimal route.

Complexity Analysis

For a graph with V vertices and E edges:

  • Sorting edges: O(E log E)
  • Union-Find operations: O(E × α(V)) ≈ O(E)
  • Total: O(E log E)

For the Advent of Code problem with ~2500 junction boxes:

  • E = C(2500, 2) ≈ 3,125,000 possible edges
  • Sorting: ~49 million comparisons
  • Union operations: ~3.1 million (nearly constant time each)

Checking every possible spanning tree instead would be exponential, so that’s out.

When to Use Kruskal’s

Kruskal’s algorithm is ideal when:

  • You need a minimum spanning tree
  • Edges can be easily sorted
  • You already have an edge list (rather than an adjacency list)
  • You care about the order edges are added (like in Day 8 Part 1: “process the first 1000 edges”)

For dense graphs or when starting from an adjacency list, Prim’s algorithm is the alternative: it builds the tree incrementally from a starting vertex and never sorts the full edge list.

Resources