MST: Kruskal & PrimMinimum spanning trees

01Why it exists

Reach for it when you see:Connect every point at the lowest total cost, no start or end specified, a cost between every pair of points, cutting the longest edges to form clusters, minimising the largest edge on a path (a bottleneck path), union-find.

02The core idea

In a connected undirected graph, a spanning tree is a choice of V − 1 edges that keeps every node connected with no cycle, and a minimum spanning tree (MST) is the one with the smallest total weight. It is not the same as a shortest-path tree: Dijkstra minimises the distance from the start to each node, while an MST cares only about the sum of all its edges. Both of the main algorithms rest on the cut property: split the nodes into two sides however you like, and the lightest edge crossing between them belongs to some minimum spanning tree. The proof is an exchange argument — if an MST does not use that edge, adding it creates a cycle, that cycle must contain another edge crossing the same split, and swapping the two cannot increase the total weight.

Kruskal is greedy from a global view. Sort every edge by weight, lightest first, and look at them one at a time: if the two ends lie in different components, take the edge and merge them; if they lie in the same component, throw it away, because there is already a path between them and adding it would close a cycle. Every edge it takes is the lightest one between its own component and everything else, which is exactly the cut property. Testing whether the ends share a component is union-find, near constant time, so the sorting dominates: O(E log E) time and O(V) extra space. It suits sparse graphs where you already have the edge list, and it can stop as soon as it has V − 1 edges.

Prim grows a single tree from one node. At every step it takes the lightest edge with one end inside the tree and one end outside, and pulls that outside node in — the cut here is "the tree" against "everything else". Keep the candidate edges in a min-heap and discard any edge whose far end has already joined the tree (the lazy version), giving O(E log E). On a dense graph — say every pair of points in the plane is an edge, so E is about V²/2 — keep an array key[v] of the lightest edge from each outside node to the tree and scan it linearly each round instead. That O(V²) is faster than the heap.

Some traps worth knowing. A disconnected graph has no spanning tree at all, so Kruskal will not reach V − 1 edges — check and report that. Writing Prim's key[v] as dist[u] + w turns it into Dijkstra; an MST compares the weight of a single edge. Neither algorithm works on a directed graph, where the minimum arborescence needs Chu–Liu/Edmonds. And union-find without path compression or union by size degrades to O(V) in the worst case. Negative weights are no problem at all, and sorting heaviest first gives you the maximum spanning tree. One especially useful property: the path between any two nodes in the MST also minimises the largest edge along the way, so Kruskal solves bottleneck-path problems too. As for the neighbouring lessons — Kruskal is the classic application of union-find, Prim's heap version is almost identical to Dijkstra apart from the value being compared, and the cut property is the textbook example of an exchange argument from greedy principles.

03The algorithm

1. 1Confirm the graph is undirected and connected. For Kruskal: sort every edge by weight, lightest first, and start union-find with each node in its own group.
2. 2Walk the edges in order. For (u, v, w), if find(u) ≠ find(v), take the edge and union the two groups; if they match, skip it, because it would close a cycle.
3. 3Stop once you have V − 1 edges. If you run out of edges with fewer than V − 1, the graph is disconnected.
4. 4For Prim: start at any node and push its incident edges into a min-heap. Pop the lightest edge each time; if its far end is already in the tree, discard it, otherwise add that node to the tree and push its edges to nodes still outside. Stop when all V nodes are in.
5. 5On a dense graph, use array Prim instead: keep key[v], the lightest edge from each outside node to the tree, add the node with the smallest key each round, and use it to update the other keys. O(V²).

04Interactive demo

The same graph of 6 nodes and 9 edges, with the two algorithms on the toggle at the top. In "Kruskal" mode the right-hand side shows the sorted edges and the current groups: B–E, A–D and A–B are taken in turn, merging A, B, D and E into one group; then B–D (4) has both ends in that group, so it goes dashed and is discarded; C–F is taken; D–E (5) is discarded for the same reason; C–E (6) joins the two groups, which completes the 5 edges, leaving B–C and E–F unexamined. In "Prim" mode the tree grows from A and the right-hand side is the min-heap: A–D, A–B and B–E come off first, then D–B and D–E pop with their far ends already in the tree and have to be dropped, and E–C and C–F finish the job. Blue edges are in the spanning tree, yellow is the edge being processed this step. Both methods pick the same edges, and both total 16.

05Code

The Python tab has union-find, Kruskal, lazy Prim, and single-linkage clustering by stopping Kruskal at k groups. The C++ tab has Kruskal via sorting plus union-find, and handles a complete graph of points in the plane with the O(V²) array version of Prim — with that many edges, listing and sorting them all is not worth it.

import heapq


class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path halving
            x = self.parent[x]
        return x

    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False                        # already one group: this edge would close a cycle
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        return True


def kruskal(n, edges):
    """edges are (u, v, w). Returns (total weight, chosen edges), or None if disconnected. O(E log E)"""
    dsu, total, chosen = DSU(n), 0, []
    for w, u, v in sorted((w, u, v) for u, v, w in edges):
        if dsu.union(u, v):
            total += w
            chosen.append((u, v, w))
            if len(chosen) == n - 1:            # V - 1 edges is a whole tree, so stop
                break
    return (total, chosen) if len(chosen) == n - 1 else None


def prim(n, edges, start=0):
    """Lazy Prim: the heap may hold stale edges with both ends in the tree; drop them on pop. O(E log E)"""
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((w, v))
        adj[v].append((w, u))
    in_tree, total, count = [False] * n, 0, 0
    heap = [(0, start)]
    while heap and count < n:
        w, u = heapq.heappop(heap)
        if in_tree[u]:
            continue
        in_tree[u] = True
        total += w                              # the edge's weight, not the distance from the start
        count += 1
        for e in adj[u]:
            if not in_tree[e[1]]:
                heapq.heappush(heap, e)
    return total if count == n else None


def clusters(points, k):
    """Single-linkage clustering: stopping Kruskal at k groups cuts the MST's k - 1 longest edges"""
    n = len(points)
    edges = sorted((abs(p[0] - q[0]) + abs(p[1] - q[1]), i, j)
                   for i, p in enumerate(points) for j, q in enumerate(points) if i < j)
    dsu, groups = DSU(n), n
    for _, i, j in edges:
        if groups == k:
            break
        if dsu.union(i, j):
            groups -= 1
    out = {}
    for i in range(n):
        out.setdefault(dsu.find(i), []).append(i)
    return sorted(out.values())


if __name__ == "__main__":
    A, B, C, D, E, F = range(6)
    edges = [(A, B, 3), (A, D, 2), (B, D, 4), (B, E, 1), (D, E, 5), (B, C, 7), (C, E, 6), (C, F, 4), (E, F, 8)]
    total, chosen = kruskal(6, edges)
    print(total, ["ABCDEF"[u] + "ABCDEF"[v] for u, v, _ in chosen])   # 16 ['BE', 'AD', 'AB', 'CF', 'CE']
    print(prim(6, edges))                       # 16: both methods always total the same
    print(kruskal(4, [(0, 1, 1), (2, 3, 1)]))   # None: disconnected, so there is no spanning tree
    pts = [(0, 0), (1, 0), (0, 1), (10, 10), (11, 10), (10, 11), (20, 0)]
    print(clusters(pts, 3))                     # [[0, 1, 2], [3, 4, 5], [6]]

06Practice

• LeetCode 1584Min Cost to Connect All Points (a complete graph, ideal for array Prim)Medium
• LeetCode 778Swim in Rising Water (a bottleneck path: add cells in increasing height order)Hard
• LeetCode 1697Checking Existence of Edge Length Limited Paths (offline queries, sorted alongside the edges)Hard
• LeetCode 1579Remove Max Number of Edges to Keep Graph Fully Traversable (two union-find structures)Hard
• LeetCode 1489Find Critical and Pseudo-Critical Edges in Minimum Spanning TreeHard