What is a minimum spanning tree, and when would you build one?
A spanning tree is a set of edges that joins every node with no cycles. A minimum spanning tree is the one whose edges add up to the smallest total weight.
So here is the example. You have five towns and you want to join them all with roads, and each road has a cost. You want the cheapest way to do it. The minimum spanning tree is the set of roads that does that.
the towns A, B, C, D, E
the roads A-B costs 4
A-C costs 1
C-B costs 2
B-D costs 5
C-D costs 8
D-E costs 3
the cheapest set A-C, C-B, B-D, D-E
the total cost 1 + 2 + 5 + 3 = 11
And when would you build one? Here are the cases.
the situation why a spanning tree
------------------------------------- ----------------------------
cheapest roads that still join no cycles, so no road
every town is paid for without need
cheapest cable layout the same idea with cables
cheapest way to connect the same idea with pipes
the pipes
And there are two things that a spanning tree always has. It has n minus one edges, where n is the number of nodes, because you need one edge less than the number of nodes to join them all without a cycle. And it is connected, so there is a route between any two nodes.
And there is a theorem that is worth knowing about. If all the edge weights are different then the minimum spanning tree is unique. If some weights are the same then there can be more than one, and they all have the same total weight.
So the rule to remember is this. A spanning tree joins every node with exactly n minus one edges and no cycles.
The next two questions in this topic show the two algorithms.