Minimum Spanning Trees

A spanning tree of a connected graph is a subgraph that is a tree and includes all vertices. A minimum spanning tree (MST) is a spanning tree whose total edge weight is as small as possible. This lesson covers two classic algorithms: Kruskal's and Prim's.

---

Definitions

Term	Definition
Spanning tree	A connected, acyclic subgraph containing all vertices
Minimum spanning tree	A spanning tree with minimum total edge weight
Properties	A spanning tree of $n$n vertices has exactly $n - 1$n−1 edges

Applications: laying cable networks, connecting computer nodes, pipe networks — any situation where you need to connect all points at minimum cost.

---

Kruskal's Algorithm

Strategy: Build the MST by adding the cheapest available edge that does not create a cycle.

Procedure

1. Sort all edges by weight (ascending).
2. Start with an empty graph (all vertices, no edges).
3. Consider the next cheapest edge:
   • If adding it would create a cycle, skip it.
   • Otherwise, add it to the tree.
4. Repeat until $n - 1$n−1 edges have been added.

Worked Example