Union-Find and Minimum Spanning Trees: Building Networks with Kruskal

Version note: The code in this post was built with .NET 10 and C# 14 and verified with xUnit v3 4.0.2 tests; measurements were taken with BenchmarkDotNet 0.15.8.

Guess First

The Bookstore customer table has accounts accumulated over the years. The marketing team asks "how many customers do we really have?". The rule is simple: accounts that share the same e-mail or the same phone belong to the same person.

CustomerAccount[] accounts =
[
    new(1, "Ada L.", ["ada@example.com"]),
    new(2, "Ada Lovelace", ["ADA@example.com", "+90 555 000 0001"]),
    new(3, "A. Lovelace", ["+90 555 000 0001", "lovelace@example.org"]),
    new(4, "Grace H.", ["grace@example.com"]),
    new(5, "Grace Hopper", ["+90 555 000 0002"]),
    new(6, "G. Hopper", ["grace@example.com", "+90 555 000 0002"]),
    new(7, "Alan T.", ["alan@example.com"]),
];

Account 1 and account 3 have no contact detail in common. Neither do accounts 4 and 5. How many real customers are there: 7, 5 or 3? And when you run this check for a million accounts, how quickly can you answer "are these two accounts already in the same group?" on every new match?

Union-Find: A Structure with Two Questions

Union-Find (a disjoint set) splits elements into disjoint groups and supports only two operations. Find(x): which group does x belong to? Union(a, b): merge a's group with b's group. Each group is kept as a tree and the root of the tree represents the group; we tell whether two elements are in the same group by comparing their roots. If the elements are ints from 0 to n-1, the whole structure is a single parent array.

The most straightforward implementation:

// No compression, no rank: correct but can degrade into long chains.
public sealed class NaiveDisjointSet
{
    private readonly int[] _parent;

    public NaiveDisjointSet(int count)
    {
        _parent = new int[count];
        for (int i = 0; i < count; i++) _parent[i] = i;
    }

    public int Find(int x)
    {
        while (_parent[x] != x) x = _parent[x];
        return x;
    }

    public bool Union(int a, int b)
    {
        int ra = Find(a), rb = Find(b);
        if (ra == rb) return false;
        _parent[ra] = rb;
        return true;
    }
}

It works correctly but has a weakness: Union does not consider which root goes under which. If you merge in the order Union(0, 1), Union(1, 2), ..., you get a chain of length n from 0 to 1, from 1 to 2, and Find(0) walks the whole chain. A real run:

naive: 10,000 Find calls on a 100,000-element chain: 961 ms
rank + compression: 10,000 Find calls: 0.06 ms

The difference on the second line comes from two small ideas.

Path Compression and Union by Rank

Union by rank: when merging, hang the shorter tree under the taller one. The rank is an upper bound on the tree height; when two trees of equal rank merge, the new root's rank goes up by one. This alone bounds the height at O(log n). Path compression: once Find has found the root, link every element on the path directly to the root; the same path is never walked again.

public sealed class DisjointSet
{
    private readonly int[] _parent;
    private readonly byte[] _rank;

    public DisjointSet(int count)
    {
        _parent = new int[count];
        _rank = new byte[count];
        for (int i = 0; i < count; i++) _parent[i] = i;
        Count = count;
    }

    public int Count { get; private set; }   // number of disjoint sets

    public int Find(int x)
    {
        int root = x;
        while (_parent[root] != root) root = _parent[root];

        // Path compression: point every node on the path straight at the root.
        while (_parent[x] != root)
        {
            int next = _parent[x];
            _parent[x] = root;
            x = next;
        }

        return root;
    }

    public bool Union(int a, int b)
    {
        int ra = Find(a), rb = Find(b);
        if (ra == rb)
        {
            return false;
        }

        // Union by rank: the shorter tree hangs under the taller one.
        if (_rank[ra] < _rank[rb]) (ra, rb) = (rb, ra);
        _parent[rb] = ra;
        if (_rank[ra] == _rank[rb]) _rank[ra]++;
        Count--;
        return true;
    }

    public bool Connected(int a, int b) => Find(a) == Find(b);
}

We deliberately wrote Find as a two-pass iterative method: the first loop finds the root, the second compresses the path. The recursive version is shorter (return _parent[x] = Find(_parent[x]);), but if the chain is long on the first call before any compression, for example when you migrate data from a naive structure, the recursion depth becomes n. The rank is a byte because with union by rank it can never exceed log₂ n; even for 2⁶⁴ elements it is 64.

With both techniques together, m operations cost O(m·α(n)) in total; α is the inverse Ackermann function, which does not exceed 5 even for n as large as the number of atoms in the universe. In practice every operation has a constant cost. This is a guarantee of the kind "a single one may be expensive but the total is cheap", that is, amortized; we explained what that means in the "Amortized Analysis: Why List<T>.Add Counts as O(1)" post of the Big-O and Complexity series. The proof rests on Tarjan's 1975 analysis and is outside the scope of this post.

The test compares the optimized version with the naive one on random operations: the speed differs, the answers must be the same.

[Fact]
public void Naive_GivesSameAnswersAsOptimized()
{
    Random random = new(11);
    DisjointSet fast = new(500);
    NaiveDisjointSet naive = new(500);
    for (int i = 0; i < 400; i++)
    {
        int a = random.Next(500), b = random.Next(500);
        Assert.Equal(naive.Union(a, b), fast.Union(a, b));
    }

    for (int i = 0; i < 1_000; i++)
    {
        int a = random.Next(500), b = random.Next(500);
        Assert.Equal(naive.Find(a) == naive.Find(b), fast.Connected(a, b));
    }
}

Merging Duplicate Customer Accounts

Back to the opening problem. Every account is an element. We keep, in a dictionary, the account where each contact detail (e-mail or phone) was first seen; if the same detail shows up again in another account, we merge the two accounts:

public sealed record CustomerAccount(int Id, string Name, string[] Contacts);

public static class AccountMerger
{
    // Accounts sharing any e-mail or phone end up in the same group.
    public static List<List<CustomerAccount>> Merge(IReadOnlyList<CustomerAccount> accounts)
    {
        DisjointSet sets = new(accounts.Count);
        Dictionary<string, int> firstOwner = new(StringComparer.OrdinalIgnoreCase);
        for (int i = 0; i < accounts.Count; i++)
        {
            foreach (string contact in accounts[i].Contacts)
            {
                if (!firstOwner.TryAdd(contact, i))
                {
                    sets.Union(i, firstOwner[contact]);
                }
            }
        }

        return [.. Enumerable.Range(0, accounts.Count)
            .GroupBy(sets.Find)
            .Select(g => g.Select(i => accounts[i]).ToList())];
    }
}

[1, 2, 3] Ada L. | Ada Lovelace | A. Lovelace
[4, 5, 6] Grace H. | Grace Hopper | G. Hopper
[7] Alan T.

The answer is 3. Accounts 1 and 3 share nothing, but both are connected through account 2: 1 and 2 share the same e-mail (differing only in case), 2 and 3 the same phone. Union-Find captures this transitivity by itself. The same goes for accounts 5 and 6. The total cost for k contact details is about O(k·α(n)), practically linear.

We could also answer the same question by building a graph and finding connected components with BFS (Breadth-First Search), as in the 15th post of the series. The difference is that Union-Find works incrementally: when a new account signs up or a customer updates their phone, you update the groups with a single Union without traversing the graph again. It has one limitation too: Union-Find cannot undo a merge. There is no "these two accounts were merged by mistake, split them" operation; you either rebuild from scratch or keep the merge decisions in a separate record.

Minimum Spanning Trees and Kruskal

The second classic use. The Bookstore will connect its offices in seven cities with fiber. Every possible line has an installation cost (units, example values). Which is the cheapest set of lines through which every office can reach every other (directly or indirectly)? This is an MST (Minimum Spanning Tree): a tree with V - 1 edges connecting V vertices with the smallest total weight.

Kruskal's algorithm (1956) applies a greedy rule: sort the edges from cheap to expensive, try each edge in order and take it if its two ends are not already connected. "Already connected?" is exactly Union-Find's job: Union returns true after merging if the two ends are in different groups, and false if they are in the same group (that is, if the edge would close a cycle).

public sealed record Link(string From, string To, int Cost);

// Kruskal: cheapest edges first, skip any edge that would close a cycle. O(E log E).
public static List<Link> Kruskal(IReadOnlyList<string> sites, IEnumerable<Link> links)
{
    Dictionary<string, int> index = sites.Select((s, i) => (s, i)).ToDictionary(x => x.s, x => x.i);
    DisjointSet sets = new(sites.Count);
    List<Link> tree = [];
    foreach (Link link in links.OrderBy(l => l.Cost))
    {
        if (sets.Union(index[link.From], index[link.To]))
        {
            tree.Add(link);
            if (tree.Count == sites.Count - 1) break;
        }
    }

    return tree;
}

string[] sites = ["Istanbul", "Ankara", "Izmir", "Bursa", "Antalya", "Konya", "Eskisehir"];
Link[] links =
[
    new("Istanbul", "Bursa", 3), new("Istanbul", "Eskisehir", 6), new("Istanbul", "Ankara", 9),
    new("Bursa", "Eskisehir", 3), new("Bursa", "Izmir", 5), new("Eskisehir", "Ankara", 4),
    new("Eskisehir", "Konya", 6), new("Ankara", "Konya", 4), new("Izmir", "Antalya", 8),
    new("Konya", "Antalya", 5), new("Izmir", "Eskisehir", 7),
];

  Istanbul - Bursa: 3
  Bursa - Eskisehir: 3
  Eskisehir - Ankara: 4
  Ankara - Konya: 4
  Bursa - Izmir: 5
  Konya - Antalya: 5
Kruskal total=24, links=6; Prim total=24; all links total=60

The 11 possible lines add up to 60 units; the MST connects the seven offices with 6 lines for 24 units. Once the sixth line is added the loop ends with break; Istanbul - Eskisehir (6) and the more expensive lines are never examined. Even if they were, it would be skipped: Istanbul and Eskisehir are already connected via Bursa, and taking that line would close a cycle. Most of the cost is in the sort: O(E log E). The Union-Find operations are almost free.

A word of caution about MSTs: the path between two offices goes through the tree and need not be the shortest path. From Antalya to Izmir the MST path goes through Konya, Ankara, Eskisehir and Bursa for 5 + 4 + 4 + 3 + 5 = 21 units, while the direct line costs 8. An MST gives "the network with the lowest total installation cost", not "the fastest route between any two points". That second question is the subject of the previous post, Dijkstra.

A Brief Look at Prim

Prim's algorithm reaches the same result another way: it starts from a single office and at each step adds the cheapest line between offices already in the network and those that are not. "The cheapest candidate line" is answered with a PriorityQueue; we use lazy deletion as in the 17th post of the series: if both ends are already in the network, skip it.

// Prim: grow one tree from a start site using a PriorityQueue. O(E log V).
public static List<Link> Prim(IReadOnlyList<string> sites, IReadOnlyList<Link> links)
{
    Dictionary<string, List<Link>> adjacent = sites.ToDictionary(s => s, _ => new List<Link>());
    foreach (Link l in links)
    {
        adjacent[l.From].Add(l);
        adjacent[l.To].Add(new Link(l.To, l.From, l.Cost));
    }

    HashSet<string> inTree = [sites[0]];
    PriorityQueue<Link, int> frontier = new();
    foreach (Link l in adjacent[sites[0]]) frontier.Enqueue(l, l.Cost);
    List<Link> tree = [];
    while (tree.Count < sites.Count - 1 && frontier.TryDequeue(out Link? link, out _))
    {
        if (!inTree.Add(link.To)) continue; // both ends already connected
        tree.Add(link);
        foreach (Link next in adjacent[link.To])
        {
            if (!inTree.Contains(next.To)) frontier.Enqueue(next, next.Cost);
        }
    }

    return tree;
}

Both find the same total, 24. With equal-weight edges they may pick different trees of equal cost; that is why the test compares the total cost rather than the lines themselves. A rough rule: if you already have an edge list and the graph is sparse, use Kruskal; if the graph is dense or kept as an adjacency list, use Prim.

Test run summary: Passed!
  total: 4
  failed: 0
  succeeded: 4
  skipped: 0
  duration: 269ms

Measurement: Naive and Optimized Union-Find

I merged 20,000 elements with their neighbors to build a long chain, then asked for the root of every element:

[Benchmark(Baseline = true)]
public long Naive()
{
    NaiveDisjointSet sets = new(N);
    for (int i = 0; i < N - 1; i++) sets.Union(i, i + 1);
    long sum = 0;
    for (int i = 0; i < N; i++) sum += sets.Find(i);
    return sum;
}

[Benchmark]
public long RankAndCompression()
{
    DisjointSet sets = new(N);
    for (int i = 0; i < N - 1; i++) sets.Union(i, i + 1);
    long sum = 0;
    for (int i = 0; i < N; i++) sum += sets.Find(i);
    return sum;
}

The measurements were taken on an Apple M5 (10 cores), macOS 27.0.1, .NET 10.0.13 and BenchmarkDotNet 0.15.8. I ran the benchmarks one at a time, but other work was running on the machine; look at the ratios, not the absolute numbers (the high standard deviation of the naive row comes from that too).

| Method             | N     | Mean          | Ratio | Allocated |
|------------------- |------ |--------------:|------:|----------:|
| Naive              | 20000 | 199,971.00 us | 1.017 |  78.15 KB |
| RankAndCompression | 20000 |      46.09 us | 0.000 |   97.7 KB |

200 ms against 46 µs, about 4,300 times. The naive version walks n²/2 = 200 million steps; the optimized version never builds the chain, because union by rank hangs every new element under the existing root and the tree height stays at 1. The 0.000 in the Ratio column is because the ratio is too small to fit in three decimals. The allocation difference is the _rank array (20,000 bytes).

Production Notes

The merge rule matters more than the algorithm. Union-Find blindly merges everything you call "the same e-mail". If you merge without lowercasing e-mails and bringing phones to a single format (for example the international E.164 format), you miss real duplicates. Conversely, shared corporate addresses like "info@" or a call center's number glue hundreds of different customers into one giant group. Real systems should route unusually large groups to review instead of merging them automatically, and record which detail caused each merge.

A union cannot be undone. To fix a wrong merge decision you either rebuild the whole structure with the remaining rules (linear cost in n and k, usually acceptable) or store the merges as a log and replay it. With customer data, keeping every match that led to a decision is a must for auditing anyway.

Map string ids to ints. DisjointSet works with int indexes; if customer ids are Guids, mapping them to 0..n-1 with a Dictionary<Guid, int> is the simplest way to keep the array-based structure. It is the same id mapping idea as in the 15th post of the series.

In network design the MST is a starting point. A single broken line splits an MST in two, because a tree has no spare path. In a real network spare lines are deliberately added on top of the MST; the algorithm gives "the cheapest connected network", not "a resilient network".

Common Pitfalls

An implementation without path compression slowing down on long chains. In small tests the naive version looks fast too; the problem only appears when real data arrives in a certain order (increasing ids, an alphabetical list). The 4,300x in the measurement is the price.

Linking elements instead of roots. Writing _parent[a] = b (without finding the roots) cuts a out of its old group; the elements below a do not move into b's group. Union must always work on roots.

Assuming _parent[x] is the root. Path compression is lazy; before Find is called, _parent[x] may not be the root. Grouping the _parent array directly when listing groups gives wrong results; call Find for every element, as in GroupBy(sets.Find).

Expecting an MST on a disconnected graph. If some offices have no lines between them at all, Kruskal returns fewer than V - 1 edges: a spanning forest. Do not report the result as "all offices connected" without checking tree.Count == sites.Count - 1.

A Small Experiment

★☆☆ Add a Size(int x) to DisjointSet that tracks the number of elements in each group (you can use union by size instead of union by rank). Print the size of the largest group in the account merging example.

★★☆ Add a safety rule to account merging: if a contact detail appears in more than 10 accounts, do not use it for merging and put it on a "needs review" list. Test with 100,000 randomly generated accounts.

★★★ Find the "critical lines" of a network: for every line in the MST, how much does the cost of the new MST rise if that line is unavailable? First write the simple version that reruns Kruskal for every line, then try to improve it to do less work.

We have finished the graph block: traversal, ordering, shortest paths and the cheapest network. The posts from here on focus on problem-solving techniques rather than data structures. The first stop is backtracking: trying all possibilities systematically, but pruning hopeless branches early. We start with permutations, subsets, N-Queens and Sudoku.