Razam Sherwani

Kruskal's Algorithm, Union-Find, and the truth behind Amortized Analysis

·13 min read·algorithmsgraph-theorydata-structures

The Minimum Spanning Tree problem

For exactly a century, computer scientists and mathematicians have wrestled with the Minimum Spanning Tree problem: how to connect every vertex in a graph using the absolute cheapest, loop-free set of edges. Specifically, in 1926 Otakar Borůvka developed the MST algorithm, Borůvka’s Algorithm, to solve the MST problem in O(Elog⁡V)\mathcal{O}(E \log V).1 Due to factors of both geographical isolation as well as aims to find a more straightforward implementation, 2 more algorithms of the same runtime, Prim’s and Kruskal’s, were invented,2 with Kruskal’s being the most elegant—in my humble opinion :)

Kruskal’s algorithm

Kruskal’s algorithm follows 2 simple steps:

  1. Sort the edges of the graph in ascending order
  2. Grab the smallest edges that you can, while skipping edges that would create a cycle, until a tree is achieved.

With this, sorting the edges with an efficient sorting algorithm would require O(Elog⁡E)\mathcal{O}(E \log E). While this seems worse than O(Elog⁡V)\mathcal{O}(E \log V), recall that a simple graph has at most V⋅(V−1)2∼V2\frac{V \cdot (V - 1)}{2} \sim V^2 edges. From this we can derive:

O(Elog⁡E)=O(Elog⁡V2)=O(2Elog⁡V)=O(Elog⁡V)\mathcal{O}(E \log E) = \mathcal{O}(E \log V^2) = \mathcal{O}(2E \log V) = \mathcal{O}(E \log V)

This seems incredibly simple, almost too good to be true in terms of a proof of correctness. It can easily be proven with the Cut Property, but that is a blog post for another time.

The bottleneck

Regardless, the algorithm seems incredibly simple to program, until you really dig into how you would ensure an edge doesn’t create a cycle. If we were to run cycle detection with DFS each time we considered an edge, it would require O(E⋅(V+E))=O(EV+E2)\mathcal{O}(E \cdot (V + E)) = \mathcal{O}(EV + E^2) which is a worse runtime than the sorting of O(Elog⁡V)\mathcal{O}(E \log V). However, we don’t. Instead, we can make use of the Union-Find data structure to do these checks in effectively O(1)\mathcal{O}(1) time (“effectively” as the true runtime is O(α(n))\mathcal{O}(\alpha(n)) amortized, but more on this later).

Union-Find

As mentioned before, Union-Find (also known as Disjoint Set Union, or DSU), is a data structure used to effectively keep track of the components of a graph. This is useful because in Kruskal’s algorithm, while we are building the tree, we will avoid adding an edge between 2 nodes of the same component, as that will produce a cycle. Specifically, it achieves this with two functions, union and find.

The version of Union-Find that we will implement conceptually works like so:

  1. On initialization, you will have n nodes. Each node has a parent, and on initialization, the parent of each node is itself.

  2. The find operation takes a node as input, and goes up the chain of parents until it reaches a node whose parent is itself, and returns the “final” parent.

  3. The union operation takes 2 nodes, and makes one of them the parent of the other.

This achieves our goal of identifying components, as you can consider the node that is its own parent as a “representative” for its own component. On initialization, every node is its own representative, so we have n nodes with no edges, and thus n components. Then we will connect the nodes u and v from each edge u-v we select. By making one of these nodes the other’s parent, they will now be in the same component, as the find operation will return the same node. This is what the code will look like for this initial implementation:

Union-Find, no rank or compressionPython · Java · Rust
class UnionFind:
    """Disjoint sets over {0, ..., n - 1}, one parent pointer per node."""

    def __init__(self, n: int) -> None:
        # Every node starts as its own representative: n nodes, n components.
        self.parent = list(range(n))

    def find(self, u: int) -> int:
        """The representative of u's component."""
        if self.parent[u] == u:
            return u
        return self.find(self.parent[u])

    def union(self, u: int, v: int) -> bool:
        """Merge the two components. False if they were already one."""
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u == root_v:
            # Same component already — an edge here would close a cycle.
            return False
        self.parent[root_v] = root_u
        return True
/** Disjoint sets over {0, ..., n - 1}, one parent pointer per node. */
static final class UnionFind {
    private final int[] parent;

    UnionFind(int n) {
        // Every node starts as its own representative: n nodes, n components.
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    /** The representative of u's component. */
    int find(int u) {
        if (parent[u] == u) {
            return u;
        }
        return find(parent[u]);
    }

    /** Merge the two components. False if they were already one. */
    boolean union(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU == rootV) {
            // Same component already — an edge here would close a cycle.
            return false;
        }
        parent[rootV] = rootU;
        return true;
    }
}
/// Disjoint sets over `0..n`, one parent pointer per node.
struct UnionFind {
    parent: Vec<usize>,
}

impl UnionFind {
    fn new(n: usize) -> Self {
        // Every node starts as its own representative: n nodes, n components.
        Self {
            parent: (0..n).collect(),
        }
    }

    /// The representative of `u`'s component.
    fn find(&self, u: usize) -> usize {
        if self.parent[u] == u {
            u
        } else {
            self.find(self.parent[u])
        }
    }

    /// Merge the two components. `false` if they were already one.
    fn union(&mut self, u: usize, v: usize) -> bool {
        let root_u = self.find(u);
        let root_v = self.find(v);

        if root_u == root_v {
            // Same component already — an edge here would close a cycle.
            false
        } else {
            self.parent[root_v] = root_u;
            true
        }
    }
}

Here we have “parent pointers” implemented as an array of size n where the element at index i is the parent of node i. It is trivial to see why union here is O(1)\mathcal{O}(1), but notice that find could be O(n)\mathcal{O}(n) in a degenerate case where we have a union of nodes that will form a linked list of length n. This is too slow, and must be improved to get our near constant time goal.

Union by rank

To avoid the degenerate case of having a linked-list-like parent chain, we always link the shorter tree to the root of the taller tree. We will track this by a new property called rank, that starts at 0, and increments each time we connect 2 trees of the same rank.

Union by rankPython · Java · Rust
class UnionFind:
    """Disjoint sets over {0, ..., n - 1}, with a parent pointer and a rank per node."""

    def __init__(self, n: int) -> None:
        # Every node starts as its own representative: n nodes, n components.
        self.parent = list(range(n))
        # A lone node is a tree of height 0.
        self.rank = [0] * n

    def find(self, u: int) -> int:
        """The representative of u's component."""
        if self.parent[u] == u:
            return u
        return self.find(self.parent[u])

    def union(self, u: int, v: int) -> bool:
        """Merge the two components, shorter tree under taller. False if already one."""
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u == root_v:
            # Same component already — an edge here would close a cycle.
            return False
        if self.rank[root_u] < self.rank[root_v]:
            self.parent[root_u] = root_v
        elif self.rank[root_u] > self.rank[root_v]:
            self.parent[root_v] = root_u
        else:
            # Equal ranks: either direction works, and the winner gets taller.
            self.parent[root_v] = root_u
            self.rank[root_u] += 1
        return True
/** Disjoint sets over {0, ..., n - 1}, with a parent pointer and a rank per node. */
static final class UnionFind {
    private final int[] parent;
    private final int[] rank;

    UnionFind(int n) {
        parent = new int[n];
        // A lone node is a tree of height 0, so rank stays all-zero here.
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            // Every node starts as its own representative: n nodes, n components.
            parent[i] = i;
        }
    }

    /** The representative of u's component. */
    int find(int u) {
        if (parent[u] == u) {
            return u;
        }
        return find(parent[u]);
    }

    /** Merge the two components, shorter tree under taller. False if already one. */
    boolean union(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU == rootV) {
            // Same component already — an edge here would close a cycle.
            return false;
        }
        if (rank[rootU] < rank[rootV]) {
            parent[rootU] = rootV;
        } else if (rank[rootU] > rank[rootV]) {
            parent[rootV] = rootU;
        } else {
            // Equal ranks: either direction works, and the winner gets taller.
            parent[rootV] = rootU;
            rank[rootU]++;
        }
        return true;
    }
}
/// Disjoint sets over `0..n`, with a parent pointer and a rank per node.
struct UnionFind {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl UnionFind {
    fn new(n: usize) -> Self {
        Self {
            // Every node starts as its own representative: n nodes, n components.
            parent: (0..n).collect(),
            // A lone node is a tree of height 0.
            rank: vec![0; n],
        }
    }

    /// The representative of `u`'s component.
    fn find(&self, u: usize) -> usize {
        if self.parent[u] == u {
            u
        } else {
            self.find(self.parent[u])
        }
    }

    /// Merge the two components, shorter tree under taller. `false` if already one.
    fn union(&mut self, u: usize, v: usize) -> bool {
        let root_u = self.find(u);
        let root_v = self.find(v);

        if root_u == root_v {
            // Same component already — an edge here would close a cycle.
            return false;
        }
        if self.rank[root_u] < self.rank[root_v] {
            self.parent[root_u] = root_v;
        } else if self.rank[root_u] > self.rank[root_v] {
            self.parent[root_v] = root_u;
        } else {
            // Equal ranks: either direction works, and the winner gets taller.
            self.parent[root_v] = root_u;
            self.rank[root_u] += 1;
        }
        true
    }
}

Here, rank essentially measures the height of our component. When you attach the root of a smaller tree to the root of a larger tree, the maximum depth doesn’t change, as the larger tree still holds the larger depth, so rank doesn’t update. However, when two trees have equal height, then the overall height grows by 1 due to the chaining.

Again, union is trivially O(1)\mathcal{O}(1). Our old runtime for find was O(n)\mathcal{O}(n), but believe it or not, this simple improvement got our runtime all the way down to O(log⁡n)\mathcal{O}(\log n). This is due to the fact that a tree whose root has rank rr contains at least 2r2^r nodes. Let’s prove this lemma first.

Lemma 1

A tree whose root has rank rr contains at least 2r2^r nodes.

Proof

Let N(r)N(r) be the minimum number of nodes required to create a tree of rank rr. We proceed to prove that

∀r N(r)≥2r\forall r\ N(r) \geq 2^r

by induction.

For our base case of r=0r = 0, a singular node has a rank of 0, so

N(0)=1N(0) = 1

Since 20=12^0 = 1, N(r)≥2rN(r) \geq 2^r holds for the base case.

For our inductive hypothesis, assume for some arbitrary rank of kk, the minimum number of nodes in a tree of rank kk is greater than or equal to 2k2^k:

N(k)≥2kN(k) \geq 2^k

For our inductive step, consider a tree of rank k+1k + 1. Under the rules of Union by rank, rank only ever increases when you perform the union of 2 trees of the same rank. As we aim to find the minimum number of nodes, the tree with the minimum number of nodes of rank k+1k + 1 would have to come from taking the union of 2 trees of rank kk, as if we take the union of a tree of rank k+1k + 1 and something smaller, we would be adding more nodes to a tree that already has a rank of k+1k + 1, so it wouldn’t be the minimum, a contradiction. Thus the minimum number of nodes of this new tree would be the sum of the minimum number of nodes of 2 trees of rank kk, thus:

N(k+1)=N(k)+N(k)N(k + 1) = N(k) + N(k)

From our inductive hypothesis of N(k)≥2kN(k) \geq 2^k, we can derive:

N(k+1)≥2k+2kN(k+1)≥2⋅2kN(k+1)≥2k+1\begin{aligned} N(k + 1) &\geq 2^k + 2^k \\ N(k + 1) &\geq 2 \cdot 2^k \\ N(k + 1) &\geq 2^{k + 1} \end{aligned}

The inductive step holds, so by mathematical induction, a tree of rank rr will always contain at least 2r2^r nodes.

This lemma is vital for proving our runtime of O(log⁡n)\mathcal{O}(\log n) that we discussed before.

Theorem 1

The find function of a Union-Find data structure with Union by rank has a runtime of O(log⁡n).\mathcal{O}(\log n).

Proof

Let nn be the total number of nodes in a specific tree of rank rr. Based on our lemma:

n≥2rn \geq 2^r

Solving for the rank rr

log⁡2(n)≥rr≤log⁡2(n)\log_2(n) \geq r \\ r \leq \log_2(n)

As the worst case for the find operation is to travel the full height (rank) of the tree to reach the representative, and the largest tree would include all nn nodes of the Union-Find data structure, it is bounded by the rank, and thus has a runtime of

O(log⁡n)\mathcal{O}(\log n)

Great! So we got O(log⁡n)\mathcal{O}(\log n), which is basically the best we can do other than constant time, right? Well, not quite, let’s introduce the next optimization.

Path compression

The idea is that every time we perform the find operation, it would be nice if we could flatten the tree out as we go, so that future find operations are faster. This is actually just a one-line change. Simply, when we go back off the recursive stack, we will reassign the parent of each node in the tree that we have visited to be directly the representative of that group, so that the next call to find on any one of these nodes is simply one step up. Let’s look at the code:

Union by rank and path compressionPython · Java · Rust
class UnionFind:
    """Disjoint sets over {0, ..., n - 1}, with a parent pointer and a rank per node."""

    def __init__(self, n: int) -> None:
        # Every node starts as its own representative: n nodes, n components.
        self.parent = list(range(n))
        # A lone node is a tree of height 0.
        self.rank = [0] * n

    def find(self, u: int) -> int:
        """The representative of u's component."""
        if self.parent[u] == u:
            return u
        # Recurse to the root, then re-hang u directly off it on the way back out —
        # every node on this path ends up one hop from the root.
        self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u: int, v: int) -> bool:
        """Merge the two components, shorter tree under taller. False if already one."""
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u == root_v:
            # Same component already — an edge here would close a cycle.
            return False
        if self.rank[root_u] < self.rank[root_v]:
            self.parent[root_u] = root_v
        elif self.rank[root_u] > self.rank[root_v]:
            self.parent[root_v] = root_u
        else:
            # Equal ranks: either direction works, and the winner gets taller.
            self.parent[root_v] = root_u
            self.rank[root_u] += 1
        return True
/** Disjoint sets over {0, ..., n - 1}, with a parent pointer and a rank per node. */
static final class UnionFind {
    private final int[] parent;
    private final int[] rank;

    UnionFind(int n) {
        parent = new int[n];
        // A lone node is a tree of height 0, so rank stays all-zero here.
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            // Every node starts as its own representative: n nodes, n components.
            parent[i] = i;
        }
    }

    /** The representative of u's component. */
    int find(int u) {
        if (parent[u] == u) {
            return u;
        }
        // Recurse to the root, then re-hang u directly off it on the way back
        // out — every node on this path ends up one hop from the root.
        parent[u] = find(parent[u]);
        return parent[u];
    }

    /** Merge the two components, shorter tree under taller. False if already one. */
    boolean union(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU == rootV) {
            // Same component already — an edge here would close a cycle.
            return false;
        }
        if (rank[rootU] < rank[rootV]) {
            parent[rootU] = rootV;
        } else if (rank[rootU] > rank[rootV]) {
            parent[rootV] = rootU;
        } else {
            // Equal ranks: either direction works, and the winner gets taller.
            parent[rootV] = rootU;
            rank[rootU]++;
        }
        return true;
    }
}
/// Disjoint sets over `0..n`, with a parent pointer and a rank per node.
struct UnionFind {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl UnionFind {
    fn new(n: usize) -> Self {
        Self {
            // Every node starts as its own representative: n nodes, n components.
            parent: (0..n).collect(),
            // A lone node is a tree of height 0.
            rank: vec![0; n],
        }
    }

    /// The representative of `u`'s component.
    fn find(&mut self, u: usize) -> usize {
        if self.parent[u] == u {
            u
        } else {
            // Recurse to the root, then re-hang u directly off it on the way back
            // out — every node on this path ends up one hop from the root.
            self.parent[u] = self.find(self.parent[u]);
            self.parent[u]
        }
    }

    /// Merge the two components, shorter tree under taller. `false` if already one.
    fn union(&mut self, u: usize, v: usize) -> bool {
        let root_u = self.find(u);
        let root_v = self.find(v);

        if root_u == root_v {
            // Same component already — an edge here would close a cycle.
            return false;
        }
        if self.rank[root_u] < self.rank[root_v] {
            self.parent[root_u] = root_v;
        } else if self.rank[root_u] > self.rank[root_v] {
            self.parent[root_v] = root_u;
        } else {
            // Equal ranks: either direction works, and the winner gets taller.
            self.parent[root_v] = root_u;
            self.rank[root_u] += 1;
        }
        true
    }
}

This dynamic reassignment of the parents of a node directly to its representative is actively destroying the height of the tree every time we traverse it. This is why we have been using the term rank, as once path compression is used height is an inaccurate term. On top of that, this complicates our runtime analysis. Because the tree is physically changing during a find operation, calculating the worst-case runtime for a singular operation no longer tells a good, accurate story. We need a different way to analyze the runtime.

What amortized analysis actually is

When we typically analyze the runtime of an algorithm in Big-O notation, we are looking for a worst-case scenario upper bound for a singular isolated operation. Amortized analysis takes a different approach. Instead, it looks at the worst-case total cost of a sequence of operations, and then divides that runtime by the number of operations.

For example, in a dynamic array, such as an ArrayList in Java, appending to the end of the list is typically O(1)\mathcal{O}(1) as you are simply inserting a value to a preallocated location in the backing array. However, when a resize is required, it will be an O(n)\mathcal{O}(n) operation to allocate a bigger array and copy all the values over. This is most people’s (including mine) first exposure to amortized analysis, where it is O(1)\mathcal{O}(1) amortized.

From here, it is a very common misconception to think of amortized analysis in this context as “an operation that is mostly O(1)\mathcal{O}(1) but sometimes O(n)\mathcal{O}(n).” While this is technically true, this is simply a coincidence. Instead, as described before, amortized analysis is a worst-case analysis of a sequence of operations. Quick proof below:

Theorem 2

Adding to the end of a dynamic list (which is initially empty with a capacity of 1, which doubles each time it’s full) is O(1)\mathcal{O}(1) amortized.

Proof

Let NN be the number of total insertions into the array, and assume that NN is a perfect power of 2, as in N=2kN = 2^k where k∈Nk \in \mathbb{N}.

Notice we have 2 potential costs. Every insertion costs exactly 1 write operation. Additionally, whenever a power of 2 is hit, reallocation and copying are required. Thus, we can say that the total amount of work is

T(N)=N+(1+2+...+2k−1)T(N) = N + (1 + 2 + ... + 2^{k-1}) \\ T(N)=N+∑i=0k−12iT(N) = N + \sum_{i=0}^{k-1} 2^i

Recall the formula for the sum of a geometric series. ∑i=0na⋅ri=a(rn+1−1r−1)\\ \sum_{i=0}^{n} a \cdot r^i = a \left( \frac{r^{n+1} - 1}{r - 1} \right)\\ Using this, we can find that T(N)=N+2k−12−1=N+2k−1=2N−1\\T(N) = N + \frac{2^k-1}{2-1} = N + 2^k - 1 = 2N - 1 \\

Computing the amortized cost you get

Amortized Cost = T(N)N=2N−1N<2=O(1)\frac{T(N)}{N} = \frac{2N - 1}{N} < 2 = \mathcal{O}(1) amortized

Back to Union-Find

How does this all apply to Union-Find? Well, when we run a sequence of mm operations (both find and union) on nn elements, we are evaluating the total cost of the operations rather than a worst-case isolated event. With path compression, a singular find operation may occasionally take O(log⁡n)\mathcal{O}(\log n). However, by updating the parent pointers along the path, we are essentially “pre-paying” for all future find operations, that will then be directly connected to their parent for a subsequent O(1)\mathcal{O}(1) lookup.

Just like the dynamic array allocation, the expensive operations alter the data structure itself to make future operations significantly cheaper. Robert Tarjan proved this exact amortized bound in 1975 by categorizing the tree ranks into expanding intervals.3 Without getting into the details (which would be redoing the entire, very long paper in all of its glory), the result is that a sequence of mm operations takes O(m⋅α(n))\mathcal{O}(m \cdot \alpha(n)) time, making an individual operation take O(α(n))\mathcal{O}(\alpha(n)) amortized time.

The inverse Ackermann function

To understand α(n)\alpha(n), we must first have a look at the Ackermann function A(m,n)A(m,n), an extremely fast growing function.4 It has the following recursive definition:

A(0,n)=n+1A(0,n) = n + 1 A(m+1,0)=A(m,1)A(m + 1, 0) = A(m,1) A(m+1,n+1)=A(m,A(m+1,n))A(m + 1, n + 1) = A(m, A(m + 1, n))

This may be hard to visualize, so here are the first few entries:

m\n0123401234512345623579113513296112541365533265536−32265536−322265536−3\begin{array}{c|ccccc} m \backslash n & 0 & 1 & 2 & 3 & 4 \\ \hline 0 & 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 3 & 5 & 7 & 9 & 11 \\ 3 & 5 & 13 & 29 & 61 & 125 \\ 4 & 13 & 65533 & 2^{65536} - 3 & 2^{2^{65536}} - 3 & 2^{2^{2^{65536}}} - 3 \end{array}

To put it into perspective, A(4,4)A(4,4) is so large that it’s incomprehensible. For example, A(4,2)A(4,2) alone has around 20,000 digits, while the number of atoms in the universe has around 80 digits.

The inverse Ackermann function α(n)\alpha(n) is the inverse of the diagonal A(n,n)A(n,n) of the Ackermann function. As it is the inverse of this rapidly growing function, it grows agonizingly slowly. As described before, if n=n = the number of atoms in the universe, α(n)<4\alpha(n) < 4.

Thus, for all practical purposes, O(α(n))\mathcal{O}(\alpha(n)) is effectively constant time. Of course, in a theoretical sense, the function still grows, so they aren’t equivalent.

This brings the magic of Kruskal’s algorithm full circle. Because we utilize this highly optimized Union-Find structure to verify components and check for cycles, the structural checks take near-constant amortized time. The O(Elog⁡V)\mathcal{O}(E \log V) sorting step remains the definitive, unavoidable bottleneck. By weaving together a straightforward greedy approach with a brilliantly self-optimizing data structure, Kruskal’s algorithm gives us an elegant solution to the Minimum Spanning Tree problem.

Footnotes

  1. Otakar Borůvka, “O jistém problému minimálním,” Práce Moravské přírodovědecké společnosti 3 (1926), 37–58. The original is in Czech; Jaroslav Nešetřil, Eva Milková and Helena Nešetřilová translate both of the 1926 papers and give the historical context in “Otakar Borůvka on minimum spanning tree problem,” Discrete Mathematics 233 (2001), 3–36. ↩

  2. Joseph B. Kruskal, “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem,” Proceedings of the American Mathematical Society 7 (1956), 48–50; R. C. Prim, “Shortest Connection Networks and Some Generalizations,” Bell System Technical Journal 36 (1957), 1389–1401. ↩

  3. Robert E. Tarjan, “Efficiency of a Good But Not Linear Set Union Algorithm,” Journal of the ACM 22 (1975), 215–225. ↩

  4. This is the two-argument Ackermann–Péter function, Rózsa Péter’s simplification of Ackermann’s original three-argument definition, and the variant the table below tabulates. ↩

← All posts

Comments

Comments load when this section nears the viewport. View the discussion on GitHub without JavaScript.

Don't have a GitHub account?

Comment here instead — it lands in the same discussion above.