Minimum spanning trees

A shortest path joins two places as cheaply as possible. Often you need something different: join every place, using as little cable, pipe or road as possible. The answer is always a special shape called a tree.

Trees and spanning trees

• A tree is a connected network with no cycles. There is exactly one path between any two of its vertices.
• A tree with $n$ vertices always has exactly $n - 1$ edges. Start with one vertex, and every edge you add brings in exactly one new vertex.
• A spanning tree of a network is a tree that uses all the vertices of the network and some of its edges.
• In a weighted network, a minimum spanning tree (MST) is a spanning tree whose total weight is as small as possible.

Why must the cheapest way to connect everything be a tree? If your design had a cycle, you could delete the most expensive edge on that cycle and everything would still be connected, for less. So the cheapest design never has a cycle.

Kruskal's algorithm

Kruskal's algorithm looks at the whole network at once:

1. List all the edges from smallest weight to largest.
2. Work down the list. Keep an edge if it does not make a cycle with the edges already kept. Skip it if it does.
3. Stop when you have kept $n - 1$ edges.

Prim's algorithm

Prim's algorithm grows one tree outwards from a starting vertex:

1. Choose any vertex to start.
2. Look at every edge that joins a vertex in the tree to a vertex not yet in the tree. Add the smallest one.
3. Repeat until every vertex is in the tree.

Prim's can never make a cycle, because each new edge always reaches a brand-new vertex. That makes it easier to use on a big diagram where cycles are hard to spot.

Your turn

Use Prim's algorithm on the Example 1 network, starting at R this time. List the edges in the order you add them.