Kruskal's Algorithm

A Bit of History

The minimum spanning tree problem has a surprisingly deep and international history. The first known algorithm was published in 1926 by Czech mathematician Otakar Borůvka, motivated by the very practical problem of designing an efficient electrical network for Moravia. His method (grow many tiny trees in parallel, then keep merging them) predates modern computers entirely. Three decades later, American mathematician Joseph Kruskal published the elegant "sort edges globally, add greedily" version presented here — in the very same 1956 issue of the Proceedings of the American Mathematical Society where he also happened to give one of the first published proofs that a related conjecture (about partial orders) held. That same year, Robert Prim independently rediscovered and refined a different MST strategy (grow a single tree outward, covered in the Prim's Algorithm deep dive) — a reminder that important algorithms are often "in the air" and discovered by multiple people from different angles at nearly the same time.

Working Principle

A minimum spanning tree (MST) of a connected, weighted, undirected graph is a subset of edges that (a) connects all vertices, (b) forms no cycle (hence "tree" — exactly \(n-1\) edges, per the induction proof in Part 1), and (c) has the smallest possible total edge weight among all such spanning trees.

Kruskal's algorithm builds one greedily:

1. Sort all edges by weight, ascending.
2. Initialize an empty edge set (the growing forest).
3. For each edge \((u,v)\) in sorted order: if \(u\) and \(v\) are not already connected by edges already chosen, add \((u,v)\) to the MST. Otherwise, skip it (adding it would create a cycle).
4. Stop once \(n-1\) edges have been added (the tree spans every vertex).

Union-Find: Detecting Cycles Fast

The one non-trivial engineering detail is step 3: "are \(u\) and \(v\) already connected?" Doing this with a fresh graph traversal every time would be far too slow. Instead, Kruskal's algorithm pairs naturally with the Union-Find (Disjoint Set Union) data structure, which tracks a partition of vertices into connected groups and supports two near-constant-time operations: find(v) (which group is \(v\) in?) and union(u, v) (merge \(u\)'s and \(v\)'s groups). Two path-compression and union-by-rank optimizations push each operation's amortized cost down to \(O(\alpha(n))\) — the inverse Ackermann function, which is less than 5 for any input size that could ever physically be stored, making it "essentially constant" in practice.

Worked Example

Four vertices \(A, B, C, D\) with edges (sorted by weight): \(A\text{-}C\) (1), \(B\text{-}C\) (1), \(B\text{-}D\) (1), \(A\text{-}B\) (4), \(C\text{-}D\) (5).

flowchart LR
    A ---|"1 (add)"| C
    B ---|"1 (add)"| C
    B ---|"1 (add)"| D
    A -.->|"4 (skip: cycle)"| B
    C -.->|"5 (skip: cycle)"| D
            

Processing in weight order: \(A\text{-}C\) (add, connects two new components), \(B\text{-}C\) (add, connects \(B\) to the growing \(\{A,C\}\) group), \(B\text{-}D\) (add, connects \(D\) — now all 4 vertices are in one component with 3 edges, exactly \(n-1\), so we stop). \(A\text{-}B\) and \(C\text{-}D\) are never even examined — the algorithm terminates as soon as the tree is complete.

Why Greedy Works: The Cut & Cycle Properties

Two lemmas, both provable by the exchange-argument style of proof by contradiction from Part 1, justify Kruskal's greediness:

• Cut property: for any partition of the vertices into two non-empty groups, the minimum-weight edge crossing that partition belongs to some MST. (If it didn't, swapping it into any candidate MST in place of a more expensive crossing edge would strictly reduce total weight — contradicting that candidate's minimality.)
• Cycle property: for any cycle in the graph, the maximum-weight edge on that cycle belongs to no MST (removing it can only ever reduce cost while an alternate path around the cycle preserves connectivity).

Kruskal's algorithm is exactly repeated application of the cut property: at every step, the cheapest untried edge is the minimum-weight edge crossing the cut between "the two components it would connect" — so adding it is always safe.

Complexity Analysis

Sorting the \(E\) edges dominates: \(O(E \log E)\). Since \(E \leq V^2\), this is also \(O(E \log V)\). The Union-Find operations that follow contribute only \(O(E\, \alpha(V))\), which is dwarfed by the sort.

$$\text{Time: } O(E \log E) \qquad \text{Space: } O(V + E)$$

Implementation

class UnionFind:
    def __init__(self, vertices):
        self.parent = {v: v for v in vertices}
        self.rank = {v: 0 for v in vertices}

    def find(self, v):
        if self.parent[v] != v:
            self.parent[v] = self.find(self.parent[v])  # path compression
        return self.parent[v]

    def union(self, u, v):
        ru, rv = self.find(u), self.find(v)
        if ru == rv:
            return False  # already connected -> would create a cycle
        if self.rank[ru] < self.rank[rv]:
            ru, rv = rv, ru
        self.parent[rv] = ru
        if self.rank[ru] == self.rank[rv]:
            self.rank[ru] += 1
        return True

def kruskal(vertices, edges):
    """edges: list of (weight, u, v). Returns (mst_edges, total_weight)."""
    uf = UnionFind(vertices)
    mst = []
    total = 0
    for weight, u, v in sorted(edges):
        if uf.union(u, v):          # only adds if it doesn't create a cycle
            mst.append((u, v, weight))
            total += weight
            if len(mst) == len(vertices) - 1:
                break
    return mst, total

vertices = ["A", "B", "C", "D"]
edges = [(1, "A", "C"), (1, "B", "C"), (1, "B", "D"), (4, "A", "B"), (5, "C", "D")]

mst, total_weight = kruskal(vertices, edges)
print("MST edges:", mst)          # [('A','C',1), ('B','C',1), ('B','D',1)]
print("Total weight:", total_weight)  # 3

#include <vector>
#include <algorithm>
#include <unordered_map>
#include <iostream>
using namespace std;

class UnionFind {
    unordered_map<string, string> parent;
    unordered_map<string, int> rank_;
public:
    UnionFind(vector<string>& vertices) {
        for (auto& v : vertices) { parent[v] = v; rank_[v] = 0; }
    }
    string find(string v) {
        if (parent[v] != v) parent[v] = find(parent[v]); // path compression
        return parent[v];
    }
    bool unite(string u, string v) {
        string ru = find(u), rv = find(v);
        if (ru == rv) return false;      // already connected
        if (rank_[ru] < rank_[rv]) swap(ru, rv);
        parent[rv] = ru;
        if (rank_[ru] == rank_[rv]) rank_[ru]++;
        return true;
    }
};

int main() {
    vector<string> vertices = {"A", "B", "C", "D"};
    // {weight, u, v}
    vector<tuple<int, string, string>> edges = {
        {1, "A", "C"}, {1, "B", "C"}, {1, "B", "D"}, {4, "A", "B"}, {5, "C", "D"}
    };
    sort(edges.begin(), edges.end());

    UnionFind uf(vertices);
    int totalWeight = 0, edgesUsed = 0;
    for (auto& [w, u, v] : edges) {
        if (uf.unite(u, v)) {
            totalWeight += w;
            edgesUsed++;
            if (edgesUsed == (int)vertices.size() - 1) break;
        }
    }
    cout << "MST total weight: " << totalWeight << endl;  // 3
    return 0;
}

import java.util.*;

class UnionFind {
    Map<String, String> parent = new HashMap<>();
    Map<String, Integer> rank = new HashMap<>();

    UnionFind(List<String> vertices) {
        for (String v : vertices) { parent.put(v, v); rank.put(v, 0); }
    }

    String find(String v) {
        if (!parent.get(v).equals(v)) {
            parent.put(v, find(parent.get(v)));  // path compression
        }
        return parent.get(v);
    }

    boolean union(String u, String v) {
        String ru = find(u), rv = find(v);
        if (ru.equals(rv)) return false;   // already connected
        if (rank.get(ru) < rank.get(rv)) { String tmp = ru; ru = rv; rv = tmp; }
        parent.put(rv, ru);
        if (rank.get(ru).equals(rank.get(rv))) rank.put(ru, rank.get(ru) + 1);
        return true;
    }
}

class Kruskal {
    record Edge(int weight, String u, String v) {}

    public static void main(String[] args) {
        List<String> vertices = List.of("A", "B", "C", "D");
        List<Edge> edges = new ArrayList<>(List.of(
            new Edge(1, "A", "C"), new Edge(1, "B", "C"),
            new Edge(1, "B", "D"), new Edge(4, "A", "B"), new Edge(5, "C", "D")
        ));
        edges.sort(Comparator.comparingInt(Edge::weight));

        UnionFind uf = new UnionFind(vertices);
        int totalWeight = 0, edgesUsed = 0;
        for (Edge e : edges) {
            if (uf.union(e.u(), e.v())) {
                totalWeight += e.weight();
                edgesUsed++;
                if (edgesUsed == vertices.size() - 1) break;
            }
        }
        System.out.println("MST total weight: " + totalWeight);  // 3
    }
}

Real-World Applications

Exercises

1. Run Kruskal's algorithm by hand on a 5-vertex graph of your own design, listing the order edges are considered and which are skipped.
2. Prove that if all edge weights in a graph are distinct, the MST is unique (hint: use the cycle property — for any two candidate MSTs, find a cycle-forming edge swap that would strictly improve one of them unless they're identical).
3. Explain why Kruskal's algorithm still works correctly (just examines more edges before finding the last useful one) if the input graph is disconnected — what does it compute instead of a single spanning tree?
4. Challenge: Implement Union-Find without path compression or union-by-rank, and construct a sequence of unions that forces \(O(n)\) time for a single find call — then explain which optimization (path compression, union by rank, or both) is responsible for preventing this degenerate case.

Limitations