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

Graph with vertices A, B, C, D, E and edges:

Edge	Weight
AB	3
AC	5
AD	8
BC	4
BD	6
CD	2
CE	7
DE	1

Sorted: DE(1), CD(2), AB(3), BC(4), AC(5), BD(6), CE(7), AD(8).

Step	Edge	Action	Reason
1	DE(1)	Add	No cycle
2	CD(2)	Add	No cycle
3	AB(3)	Add	No cycle
4	BC(4)	Add	No cycle (connects {A,B} to {C,D,E})
5	AC(5)	Reject	Creates cycle A-B-C-A

MST edges: DE, CD, AB, BC. Total weight: 1 + 2 + 3 + 4 = 10.

We have 4 edges connecting 5 vertices — a valid spanning tree.

Exam Tip: Show your sorted edge list and justify each "add" or "reject" decision. Mark which cycle would be created when rejecting an edge.

---

Prim's Algorithm (Graphical/Network Method)

Strategy: Grow the tree from a starting vertex by always adding the cheapest edge that connects a vertex in the tree to a vertex not yet in the tree.

Procedure

1. Choose a starting vertex (any vertex).
2. Mark it as "in the tree".
3. Find the cheapest edge from a tree vertex to a non-tree vertex.
4. Add this edge and the new vertex to the tree.
5. Repeat until all vertices are in the tree.

Worked Example (same graph, starting at A)