Minimum Spanning Tree

The questions so far concerned the path between two vertices. This lesson changes the question: what is the cheapest set of edges that connects all vertices to each other?

The question is the basic form of network design: every point must be connected, and the total cable, pipe, or line cost must be minimized.

The Problem

In a weighted, undirected, connected graph, a spanning tree is a subgraph that includes every vertex and contains no cycle. Such a subgraph has exactly $V-1$ edges.

A minimum spanning tree (MST) is the spanning tree whose sum of edge weights is smallest. If the weights are all distinct, the MST is unique; if equal weights exist, more than one MST may exist, and all of them have the same total weight.

The graph used throughout this lesson is undirected:

edges: list[tuple[int, str, str]] = [
    (4, "A", "B"), (2, "A", "C"), (5, "B", "C"),
    (10, "B", "D"), (3, "C", "E"), (4, "E", "D"), (11, "D", "F"),
]
vertices = ["A", "B", "C", "D", "E", "F"]

The Cut Property

Both algorithms are greedy, and their correctness rests on a single observation.

A cut splits the vertices into two non-empty parts. An edge crosses the cut if its endpoints lie in different parts.

Cut property: The lightest edge crossing any cut is present in some minimum spanning tree.

The justification is an exchange argument. Let $e$ be the lightest crossing edge, and consider an MST that does not contain it. Adding $e$ to this tree creates a cycle; the cycle must cross the cut at least once more. Let that crossing edge be $f$. Removing $f$ and adding $e$ yields another spanning tree whose weight has not increased, because $e \leq f$. Hence an MST containing $e$ also exists.

This property justifies every greedy strategy of the form “take the cheapest edge that is currently safe.” The two algorithms differ only in which cut they look at.

Prim’s Algorithm

The tree starts from a single vertex and grows on every step. The cut examined is the one between the vertices already in the tree and those outside it; the edge chosen is the lightest one crossing this cut.

import heapq
from collections import defaultdict


def build_adjacency(edges: list[tuple[int, str, str]]) -> dict[str, list[tuple[int, str]]]:
    adjacency: dict[str, list[tuple[int, str]]] = defaultdict(list)
    for weight, v, w in edges:
        adjacency[v].append((weight, w))
        adjacency[w].append((weight, v))
    return adjacency


def prim(edges: list[tuple[int, str, str]],
         start: str) -> tuple[list[tuple[int, str, str]], int]:
    adjacency = build_adjacency(edges)
    in_tree = {start}
    queue = [(weight, start, w) for weight, w in adjacency[start]]
    heapq.heapify(queue)
    tree: list[tuple[int, str, str]] = []

    while queue:
        weight, v, w = heapq.heappop(queue)
        if w in in_tree:                # both ends already in the tree: cycle
            continue
        in_tree.add(w)
        tree.append((weight, v, w))
        for edge_weight, neighbor in adjacency[w]:
            if neighbor not in in_tree:
                heapq.heappush(queue, (edge_weight, w, neighbor))
    return tree, sum(weight for weight, _, _ in tree)


print(prim(edges, "A"))
# ([(2, 'A', 'C'), (3, 'C', 'E'), (4, 'A', 'B'), (4, 'E', 'D'), (11, 'D', 'F')], 24)

The structure closely resembles Dijkstra’s algorithm; the only difference is that the priority is distance to the tree, not distance from the source. The cost is also the same: $O(E \log V)$ with a binary heap.

Kruskal’s Algorithm

Kruskal does not grow a tree; it sorts the edges by weight and adds them in order. An edge is skipped when its two endpoints are already in the same component, since adding it would create a cycle.

This check uses a union-find structure: a structure that reports, at nearly constant cost, which component each vertex belongs to.

class UnionFind:
    def __init__(self, vertices: list[str]) -> None:
        self.parent = {v: v for v in vertices}
        self.rank = {v: 0 for v in vertices}

    def find(self, v: str) -> str:
        while self.parent[v] != v:
            self.parent[v] = self.parent[self.parent[v]]   # path compression
            v = self.parent[v]
        return v

    def union(self, a: str, b: str) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                                    # already the same component
        if self.rank[ra] < self.rank[rb]:                    # union by rank
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True


def kruskal(edges: list[tuple[int, str, str]],
            vertices: list[str]) -> tuple[list[tuple[int, str, str]], int]:
    components = UnionFind(vertices)
    tree: list[tuple[int, str, str]] = []
    for weight, v, w in sorted(edges):
        if components.union(v, w):
            tree.append((weight, v, w))
            if len(tree) == len(vertices) - 1:      # tree complete
                break
    return tree, sum(weight for weight, _, _ in tree)


print(kruskal(edges, vertices))
# ([(2, 'A', 'C'), (3, 'C', 'E'), (4, 'A', 'B'), (4, 'E', 'D'), (11, 'D', 'F')], 24)

The two algorithms find the same tree on this graph. In general only the total weight is guaranteed to match; if equal-weight edges exist, they can produce different trees of equal total weight.

The cut here is “the component of one endpoint of the edge being tried” versus the remaining vertices; the edge is the lightest one crossing that cut, because lighter ones have already been tried.

When path compression and union by rank are used together, the amortized cost of union-find operations is nearly constant — its growth is bounded by the inverse Ackermann function and is smaller than four in practice.

Comparison

Criterion	Prim	Kruskal
Approach	Grow the tree	Add edges in order
Helper structure	Priority queue	Union-find
Cost	$O(E \log V)$	$O(E \log E)$
Dense graph	Suits it (array variant gives $O(V^2)$)	Sorting dominates
Disconnected graph	Finds only one component	Produces a spanning forest

Sorting dominates Kruskal’s cost; if the edges are already sorted, the cost drops to nearly linear. Prim gains the edge as the edge count approaches the square of the vertex count.

One distinction is decisive in practice: if the graph is not connected, Kruskal produces one tree per component, and the result is a spanning forest; Prim covers only the component of the starting vertex.

A Clustering Application

Kruskal’s intermediate steps are meaningful on their own: when the algorithm has added $V-k$ edges, $k$ components remain, and these components are the $k$ clusters that are farthest apart from each other.

This is the single-linkage clustering method: distances between points are treated as edge weights, an MST is built, and the heaviest $k-1$ edges are discarded. The result is the split that maximizes the minimum distance between clusters.

The same structure is also used in network design and in approximate solutions: in the metric case of the traveling salesman problem, the MST gives a lower bound on the length of the optimal tour and helps produce a tour that does not exceed twice that length.

Summary

• A spanning tree connects all vertices acyclically and contains $V-1$ edges; a minimum spanning tree is the lightest of these.
• The cut property states that the lightest edge crossing any cut is present in some MST, and it justifies the greedy choices.
• Prim grows a tree and uses a priority queue; its cost is $O(E \log V)$.
• Kruskal sorts edges and checks cycles with union-find; its cost is $O(E \log E)$.
• Path compression and union by rank make union-find operations amortized nearly constant.
• Kruskal’s intermediate states produce clustering; an MST also provides a lower bound in approximate solutions.

Next Step

Until now, edges carried a cost. The next lesson gives edges a different meaning: capacity. How much can be pushed from a source to a target through a network is now an optimization problem defined on a graph, and its answer arrives with an unexpected equality — the equality between maximum flow and minimum cut.