12.1 Minimum Spanning Tree Algorithms (Prim's and Kruskal's)

Minimum Spanning Tree Algorithms

A Minimum Spanning Tree (MST) is the cheapest way to connect every node in a weighted, undirected graph without forming any cycles. MST algorithms show up constantly in network design problems: laying cable between buildings, connecting routers, or planning road systems where you want full connectivity at minimum cost.

This section covers the two classic MST algorithms, Prim's and Kruskal's, along with the properties that make MSTs work.

Minimum Spanning Tree Algorithms

Minimum spanning tree properties

An MST is a subset of edges from a weighted, connected, undirected graph that connects all vertices with the lowest possible total edge weight. Because it's a tree, it contains no cycles, and it always has exactly $V - 1$ edges for $V$ vertices.

Whether a graph has one unique MST or several valid ones depends on the edge weights:

• Distinct edge weights guarantee a unique MST.
• Duplicate edge weights can produce multiple valid MSTs (each with the same total weight, but using different edges).

Two properties are especially useful for proving correctness of MST algorithms:

• Cut property: Take any cut (a partition of vertices into two groups). The minimum-weight edge crossing that cut must be in the MST. This is why greedy choices work: picking the lightest crossing edge is always safe.
• Cycle property: For any cycle in the graph, the heaviest edge in that cycle is not in the MST. If it were included, you could swap it out for a cheaper edge and reduce total weight.

Steps of Prim's algorithm

Prim's grows the MST outward from a single starting vertex, always attaching the nearest reachable vertex. Think of it as expanding a connected region one vertex at a time.

1. Initialize an empty set to hold MST vertices. Assign a key value to every vertex: set the starting vertex's key to 0 and all others to infinity.
2. While there are vertices not yet in the MST:
   1. Select the vertex with the smallest key value that isn't in the MST yet.
   2. Add that vertex to the MST set.
   3. For each neighbor of the newly added vertex, check: is the edge weight to that neighbor less than the neighbor's current key? If so, update the neighbor's key to the smaller weight (and record which edge produced it).
3. Stop when all vertices are in the MST. The recorded edges form the tree.

The key values act as "best known cost to reach this vertex from the MST so far." A priority queue (typically a binary heap) makes step 2.i efficient by quickly extracting the minimum-key vertex.

Steps of Kruskal's algorithm

Kruskal's takes a different approach: instead of growing from one vertex, it considers all edges globally, cheapest first, and merges components together.

1. Sort all edges in non-decreasing order of weight.
2. Initialize an empty edge set for the MST. Create a disjoint-set (union-find) data structure where each vertex starts in its own component.
3. Iterate through the sorted edges, from lightest to heaviest:
   1. For the current edge $(u, v)$, use Find to check whether $u$ and $v$ are in the same component.
   2. If they're in different components, add the edge to the MST and call Union to merge their components.
   3. If they're already in the same component, skip the edge (adding it would create a cycle).
4. Stop once the MST contains $V - 1$ edges.

Cycle detection here is handled entirely by the union-find structure. Two vertices in the same set are already connected, so any edge between them would close a cycle.

Prim's vs Kruskal's algorithms

Both algorithms are greedy: they make locally optimal choices that lead to a globally optimal MST. When all edge weights are distinct, they produce the exact same tree.

Time complexity

When to use which

• Prim's works well on dense graphs (many edges) because it processes vertices via a priority queue and pairs naturally with an adjacency matrix. It doesn't need to sort all edges upfront.
• Kruskal's tends to be faster in practice on sparse graphs (few edges) because sorting a small edge list is cheap, and the union-find operations are nearly constant time.