Graphs 0/61

Union-find (DSU): merging disjoint sets · 2 of 2

Minimum spanning trees

Connect every vertex for the lowest total weight with Kruskal’s algorithm and union-find, see why each lightest edge is safe to take, and use Prim’s algorithm when the graph is dense.

2,370 words · 11 min read

Part 1 of 6 Minimum spanning trees

The cheapest roads that connect every town

Five towns are to be joined by roads. A survey has found seven places where a road could be built and what each would cost, and we want to build roads that connect all the towns for the smallest total cost. As a graph, the towns are vertices and the possible roads are undirected edges. The cost of a road is a number attached to its edge, called the weight of the edge, and a graph whose edges carry weights is a weighted graph.

The five towns

The number on each road is its cost:

123458901234

Every cost here is positive, so the roads we build should not contain a cycle. If they did, we could leave out one road of the cycle and save its cost, and the towns would still be connected. A connected graph without a cycle is a tree, and a tree with nn vertices has n−1n - 1 edges. So we are looking for a tree made of 4 of the 7 roads.

A tree that is made of edges of a graph and contains all of its vertices is called a spanning tree of the graph. Its weight is the sum of the weights of its edges, and a spanning tree whose weight is as small as possible is a minimum spanning tree (MST).

The roads 0-1, 1-3, 2-3 and 2-4 form a spanning tree of weight 4+5+8+9=264 + 5 + 8 + 9 = 26. The roads 0-2, 1-2, 1-3 and 3-4 form another one, of weight 1+2+5+3=111 + 2 + 5 + 3 = 11, and this page will show that no spanning tree of the five towns is lighter.

With 7 roads we could try every set of 4, since there are only 35 such sets. That stops being possible very soon: a graph with 20 vertices and 40 edges has more than 101110^{11} sets of 19 edges.