Spanning Trees & Minimum Spanning Trees: Kruskal & Prim

A spanning tree of a graph is a tree built from the graph's own edges that still reaches every vertex. When each edge has a cost or weight — cable length, road distance, construction price — the cheapest possible spanning tree is the minimum spanning tree (MST). Two classic greedy algorithms find it: Kruskal's algorithm and Prim's algorithm.

MSTs matter wherever you must connect everything as cheaply as possible: laying the least cable to wire a campus, designing the shortest road network between towns, or clustering data points.

Key Concepts

• Weighted graph: every edge carries a number (its weight or cost).
• Spanning tree: n − 1 edges that connect all n vertices with no cycles.
• Minimum spanning tree: the spanning tree with the smallest total weight; several MSTs can share the same minimum total.
• Kruskal's algorithm: sort all edges by weight, then add them one by one, skipping any edge that would form a cycle.
• Prim's algorithm: start from any vertex and repeatedly add the cheapest edge connecting the growing tree to a new vertex.
• Cut property: the reason both work — for any split of vertices into two groups, the cheapest crossing edge belongs to some MST.

How It Works

Kruskal's steps: (1) sort all edges cheapest first; (2) walk down the list, adding an edge only if its endpoints are not already connected through chosen edges; (3) stop at n − 1 edges. Prim's steps: (1) pick any start vertex as "in the tree"; (2) add the cheapest edge from in-tree vertices to outside vertices, marking its new endpoint in-tree; (3) repeat until all vertices are in. Both are greedy, and the cut property guarantees greed never goes wrong.

Worked Example

Connect 4 towns A, B, C, D with road costs: A–B = 4, A–C = 3, A–D = 7, B–C = 5, B–D = 6, C–D = 2. Kruskal: sorted edges are C–D(2), A–C(3), A–B(4), B–C(5), B–D(6), A–D(7). Take C–D (2), then A–C (3), then A–B (4) — all 4 towns are now connected with 3 edges, so stop. MST total = 2 + 3 + 4 = 9. Prim from A: cheapest edge from {A} is A–C (3); from {A, C} the cheapest outward edge is C–D (2); from {A, C, D} the cheapest outward edge is A–B (4). Same tree, same total 9. Any other spanning tree costs more — for example A–B, B–C, C–D costs 4 + 5 + 2 = 11.

Common Misconceptions

• The MST is not the same as shortest paths. An MST minimises the total of all its edges; shortest-path trees minimise each individual route from one source. The two trees usually differ.
• Greedy does not always work — but it does here. For most optimisation problems, always grabbing the cheapest option fails. MSTs are special: the cut property is the proof that greed is safe.
• The MST need not be unique. With equal-weight edges, different MSTs can exist — but every MST has the same minimum total weight.

Real-World Applications

• Network cabling: wiring every building on a campus with the least total cable.
• Road and pipeline layout: connecting towns or oil wells at minimum construction cost.
• Clustering: removing the most expensive MST edges splits data into natural groups.
• Approximation algorithms: doubling an MST gives a route at most twice the optimal travelling-salesperson tour length.

A spanning tree connects everything with n − 1 edges, and the minimum spanning tree does it cheapest. Kruskal sorts edges and skips cycle-makers; Prim grows one tree by always adding its cheapest outward edge.