Minimum Spanning Trees: Kruskal's & Prim's Algorithms

Graph Theory

Chapter 8 · Minimum Spanning Trees: Kruskal's & Prim's Algorithms

Chapters 6 and 7 answered "what's the cheapest way from one vertex to the others?" This chapter asks a genuinely different question: given a weighted, undirected, connected graph, what's the cheapest possible way to connect every vertex to every other, using as few edges as it takes and nothing more?

What a Minimum Spanning Tree Actually Is

A spanning tree of a connected graph with V vertices is a subgraph that connects all V vertices using exactly V − 1 edges, with no cycles — precisely the tree definition Chapter 4's own finding-box already established. A Minimum Spanning Tree (MST) is the spanning tree whose edge weights sum to the smallest possible total, out of every spanning tree the graph could have.

Two genuinely different greedy strategies

Kruskal's algorithm is greedy on edges — always consider the cheapest remaining edge, anywhere in the graph. Prim's algorithm is greedy on the frontier — always grow the tree by whichever cheapest edge connects something already in the tree to something not yet in it (a close cousin of Chapter 6's own Dijkstra).

Method 1: Kruskal's Algorithm

Sort every edge in the graph by weight, ascending. Go through them one at a time: add an edge to the MST unless both of its endpoints are already connected to each other through edges already added — adding it anyway would create a cycle, which a tree can never have.

Checking "already connected" with Union-Find

A Union-Find (Disjoint Set) structure tracks which component each vertex currently belongs to. find(x) returns x's component; union(x, y) merges two components into one. An edge is safe to add exactly when find(u) != find(v) — its two endpoints are still in different components.

Graph: A-B(4), A-C(2), B-C(1), B-D(5), C-D(8), C-E(10), D-E(2), B-E(6).

Traced and verified directly, in ascending weight order

B-C(1): different components — add. A-C(2): different components — add. D-E(2): different components — add. A-B(4): A and B already connected via B-C-A — skip, would form a cycle. B-D(5): different components (the {A,B,C} group and the {D,E} group) — add. Every remaining edge (B-E, C-D, C-E) now connects vertices already in the same component — all skipped. Final MST: {B-C, A-C, D-E, B-D}, total weight 10.

Method 2: Prim's Algorithm

Start from any single vertex — it's the entire "tree" so far. Repeatedly find the cheapest edge connecting a vertex already in the tree to one that isn't, add that edge and vertex, and repeat until every vertex is included. A priority queue does the "cheapest available edge" lookup, exactly like Dijkstra's own priority queue found the cheapest available distance.

Same graph, starting from A:

Traced and verified directly

Frontier from {A}: cheapest is A-C(2) — add C. Frontier from {A,C}: cheapest is C-B(1) — add B. Frontier from {A,B,C}: cheapest is B-D(5) — add D. Frontier from {A,B,C,D}: cheapest is D-E(2) — add E. Final MST: {A-C, C-B, B-D, D-E}, total weight 10 — the exact same total, and in fact the exact same set of edges, as Kruskal's algorithm found, just discovered in a different order.

Same total weight is guaranteed — the exact edges usually aren't

Both algorithms are provably correct, so they always agree on the total MST weight. When a graph has no weight ties among the edges that matter, as here, they typically land on the identical edge set too — but with ties present, they can legitimately pick different edges of equal weight and still both be correct, exactly like the non-unique topological orders from Chapter 5.

Real Relevance: Network Design

Laying fiber or cable to connect a set of offices, data centers, or towns at minimum total cost is precisely the MST problem — vertices are sites, edge weight is the cost of a direct link between two sites, and the MST is the cheapest possible way to make sure every site can reach every other (even if only indirectly, through other sites on the tree). The same shape shows up in circuit board wiring and in clustering algorithms that group data points by cutting the most expensive edges out of an MST.

Kruskal's & Prim's in Code

def kruskal(vertices, edges):
    parent = {v: v for v in vertices}
    def find(x):
        while parent[x] != x:
            x = parent[x]
        return x
    def union(x, y):
        parent[find(x)] = find(y)

    mst, total = [], 0
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        if find(u) != find(v):
            union(u, v)
            mst.append((u, v, w))
            total += w
    return mst, total

import heapq
def prim(vertices, adj, start):
    visited = {start}
    heap = list(adj[start])   # (weight, u, v) tuples
    heapq.heapify(heap)
    mst, total = [], 0
    while heap and len(visited) < len(vertices):
        w, u, v = heapq.heappop(heap)
        if v in visited:
            continue
        visited.add(v)
        mst.append((u, v, w))
        total += w
        for w2, u2, v2 in adj[v]:
            if v2 not in visited:
                heapq.heappush(heap, (w2, v, v2))
    return mst, total

Hands-On Exercises

Exercise 1

Using Kruskal's algorithm, find the MST of the graph with edges P-Q(3), P-R(1), Q-R(4), Q-S(2), R-S(5). Show which edges are added and which are skipped, and the total weight.

📄 View solution

Exercise 2

Four offices need network cabling: Office1-Office2(8), Office1-Office3(5), Office2-Office3(3), Office2-Office4(9), Office3-Office4(4). Using Prim's algorithm starting from Office1, find the minimum-cost cabling plan and its total cost.

📄 View solution

Exercise 3

Explain why Kruskal's algorithm needs a Union-Find structure to detect cycles, while Prim's algorithm never risks creating a cycle at all — even without any cycle-checking step of its own.

📄 View solution

Chapter 8 Quick Reference

Spanning tree: connects all V vertices using exactly V−1 edges, no cycles (Chapter 4's own tree definition)
Kruskal's algorithm: sort all edges by weight; add each one unless it connects two vertices already in the same component (Union-Find)
Prim's algorithm: grow one tree from a start vertex, always adding the cheapest edge on the current frontier — a close cousin of Dijkstra
Both algorithms always agree on the total MST weight; they agree on the exact edges too unless weight ties allow more than one valid MST
Real use: minimum-cost network/cable design, circuit wiring, clustering
Next chapter: Trees as a special case of graphs — structure and traversal