Edexcel A Level Further Maths · Decision 1
Minimum Spanning Trees
The big idea: when you need to connect a bunch of places together as cheaply as possible — with no wasted extra connections and no wasted loops — you're looking for a minimum spanning tree, and Kruskal's and Prim's algorithms are just two different systematic ways of building one.
SummaryEverything in this chapter, at a glance
- A network is a weighted graph — vertices (nodes) joined by edges (arcs) that carry a "weight" like distance, cost, or time.
- Networks can be represented as adjacency matrices (counts of direct connections) or distance matrices (weights of connections).
- A spanning tree connects every vertex in a network using the fewest possible edges, with no cycles.
- A minimum spanning tree (MST) is the spanning tree with the smallest possible total weight.
- Kruskal's algorithm builds the MST by sorting all edges by weight and greedily adding the cheapest one that doesn't create a cycle — it works well from a list of edges or a graph.
- Prim's algorithm builds the MST by growing outward from a single starting vertex, always adding the cheapest edge that connects the "grown" tree to a new vertex — it works well from a graph a matrix.
- Both algorithms always find minimum spanning tree — they might select edges in a different order, but the total weight will be the same.
- The number of edges in any spanning tree of a network with
n vertices is always n − 1.
1. Networks & MatricesThe language you need before you touch an algorithm
What is a network?
Think of a network as a map. The dots on the map are called vertices (or nodes) — these might represent towns, computers, or buildings. The lines connecting the dots are called edges (or arcs) — these represent a road, a cable, a flight route, whatever links two places together.
What makes a network special (compared to just any graph) is that every edge has a weight attached to it — a number representing something real, like distance in km, cost in £, or time in minutes. That's why a network is formally called a weighted graph.
Analogy
Imagine a road map of five towns where every road has a "toll price" written on it. That map — towns as dots, roads as lines, toll prices as weights — a network. Everything in this chapter is really just: "what's the cheapest way to connect all five towns using some of these roads?"
Adjacency matrix vs. distance matrix
A matrix is just a table used to store all the connection information about a network in a grid, instead of drawing it out. There are two matrix types you need to tell apart:
Adjacency matrix
This tells you how many direct connections exist between each pair of vertices — it does care about weight, only about "is there a link, and if so how many?" Every vertex is listed as both a row heading and a column heading, so the matrix is always square.
- An entry of
0 means no direct connection between that pair of vertices.
- In a simple graph, entries are only ever 0 or 1.
- A loop (an edge that starts and ends at the same vertex) shows up on the leading diagonal (top-left to bottom-right). In an matrix this value is
2, because you can travel round the loop in two directions. In a matrix it's 1, because the loop only goes one way.
- undirected
Distance matrix
weight
directed
two separate directed edges