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:
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 vertices has 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 . The roads 0-2, 1-2, 1-3 and 3-4 form another one, of weight , 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 sets of 19 edges.
Kruskal's algorithm
Kruskal's algorithm builds a minimum spanning tree from the lightest edges:
- Sort the edges by weight, lightest first.
- Start with no edge chosen, so that every vertex is a component by itself.
- Go through the edges in sorted order. If the two ends of an edge are in different components, take the edge, which merges the two components. If they are in the same component, skip the edge, because it would close a cycle.
When the graph is connected, the edges taken form a minimum spanning tree. The table shows the algorithm on the five towns.
| Road | Cost | Components before the road | Decision |
|---|---|---|---|
| 0-2 | take | ||
| 1-2 | take | ||
| 3-4 | take | ||
| 0-1 | skip: 0 and 1 are joined through 2 | ||
| 1-3 | take | ||
| 2-3 | skip | ||
| 2-4 | skip |
Four roads are taken, 0-2, 1-2, 3-4 and 1-3, and their costs add up to . After the fourth of them all five towns are in one component, so every later road is skipped, and the loop could stop there.
Step 3 asks of every edge whether its two ends are in the same component, and merges the two components when they are different. A search could answer the question, at a cost of up to steps for each of the edges, which for vertices and edges comes to steps. But the question and the merge are the two operations of union-find, and a single call does both: union(a, b) merges the components of and if they differ and returns false if they are the same.
Replay the run with union-find
The widget is a union-find structure on the five towns, with the seven roads in sorted order. Each press of the first button adds the next road, which is one row of the table. A road that merges two groups is one that Kruskal's algorithm takes, and a road whose ends have the same root already is one that it skips. The fourth road, 0-1, is the first to be skipped.
Why Kruskal's algorithm is correct
Kruskal's algorithm never takes back an edge, so we have to be sure that an edge it takes cannot be a mistake. We look at one decision first, the moment at which the road 1-3 of cost 5 is taken. At that moment the towns are in two components, and .
The roads that leave a component
The drawing shows the component of town 1 and the three roads that lead out of it:
- roads taken so far
- the component of town 1, and the road 1-3
- the skipped road 0-1
The roads that leave the component are 1-3 with cost 5, 2-3 with cost 8 and 2-4 with cost 9. The road 1-3 is the cheapest of them. Every cheaper road came earlier in the sorted order, and a road that has been dealt with has both ends in one component, whether it was taken or skipped, so no cheaper road can lead out of this component.
Now take any spanning tree that does not use the road 1-3, for example the roads 0-2, 1-2, 3-4 and 2-3, which weigh 14 together. The tree connects towns 1 and 3 by some path, here 1, 2, 3. That path starts inside the component and ends outside it, so it uses one of the other roads that leave the component, here 2-3.
We remove that road and add 1-3. Removing 2-3 splits the tree into two pieces with town 1 in one and town 3 in the other, and 1-3 joins the pieces again, so the result is a spanning tree. Its weight is . The road we removed also leaves the component, so it costs at least as much as 1-3, and the new tree is at most as heavy as the old one.
Nothing in this exchange depends on the five towns. Whenever Kruskal's algorithm takes an edge , no edge that leaves the component of one of its ends costs less than , for the reason given above. A spanning tree without has a path between the two ends of , and that path leaves the component along some other edge , which costs at least as much as . Removing and adding gives a spanning tree that is no heavier.
So start with a minimum spanning tree, and go through the edges of the algorithm in the order in which it took them. If the tree contains the edge, leave the tree as it is. If it does not, make the exchange, which brings the edge in without raising the weight.
The edge that goes out is never one of the algorithm's earlier edges, which the tree already contains. When the algorithm takes , each of its earlier edges has both ends in one component, while the edge that goes out has its ends in two. So no step removes an edge of the algorithm, and at the end the tree consists of the edges of the algorithm. Its weight has not gone up, so the tree of the algorithm is a minimum spanning tree too.
The fact behind the exchange is known as the cut property: divide the vertices of a graph into two sets in any way, and the lightest edge that runs between the two sets can be part of a minimum spanning tree.
The argument compares weights and uses nothing else about them, so it also holds when several edges have the same weight and when weights are negative. Sorting the edges from heaviest to lightest gives a maximum spanning tree for the same reason.
Kruskal's algorithm in code
In some problems the graph is not handed over as a list of edges, and making that list is the first step:
You get distinct points with integer coordinates. Connecting points and costs their Manhattan distance, .
Return the minimum total cost of connections that link every point to every other one, directly or through other points.
Constraints
- All points are distinct
Sample 1 · Input
points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output
20
Sample 2 · Input
points = [[3,12],[-2,5],[-4,1]]
Output
18
The cost of connecting two points is the difference of their coordinates plus the difference of their coordinates. In the second sample the three pairs of points cost , and . Kruskal's algorithm takes 6 and 12 and skips 18, and the answer is .
Any two points may be connected, so the graph has an edge for every pair of points. For 1,000 points that is
The program lists them as triples with the cost in front, so that sorting the triples sorts the edges by cost. The loop after the sort is Kruskal's algorithm:
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, v):
root = v
while self.parent[root] != root:
root = self.parent[root]
while self.parent[v] != root: # path compression
above = self.parent[v]
self.parent[v] = root
v = above
return root
def union(self, a, b):
a, b = self.find(a), self.find(b)
if a == b:
return False
if self.size[a] < self.size[b]: # union by size
a, b = b, a
self.parent[b] = a
self.size[a] += self.size[b]
return True
def min_cost_connect_points(points):
n = len(points)
edges = []
for i in range(n):
for j in range(i + 1, n):
cost = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
edges.append((cost, i, j))
edges.sort() # by cost, because the cost comes first
dsu = DSU(n)
total = 0
for cost, i, j in edges:
if dsu.union(i, j): # true for the edges that are taken
total += cost
return total
print(min_cost_connect_points([[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]))
print(min_cost_connect_points([[3, 12], [-2, 5], [-4, 1]]))The program prints 20 and 18 for the two samples. Sorting is the expensive part:
The points of this problem can always be connected. A graph that is given by its edges may not be connected, and then it has no spanning tree. Kruskal's algorithm shows this by taking fewer than edges, so a program that may meet such a graph counts the edges it takes.
Prim's algorithm
Prim's algorithm finds a minimum spanning tree in a different order. It grows one tree from a starting vertex, and at every step it adds the lightest edge that leads from the tree to a vertex outside it. That edge is the lightest one between the vertices of the tree and all the others, so the exchange from the proof for Kruskal's algorithm brings it into a minimum spanning tree without raising the weight. The edge that the exchange removes has one end in the tree and the other outside it, while every edge chosen before has both ends in the tree, so none of those is removed.
On the five towns, starting from town 0, the first road is 0-2 with cost 1. The roads that leave cost 4, 2, 8 and 9, so 1-2 is next. From the lightest road out is 1-3 with cost 5, and from it is 3-4 with cost 3. These are the four roads of Kruskal's algorithm, taken in another order.
To find the lightest edge out of the tree, the algorithm keeps an array best, in which best[v] is the weight of the lightest edge between and the tree, or when there is no such edge yet. The starting vertex gets the entry 0, so that it is picked first. Each step picks the vertex outside the tree with the smallest entry and adds it. Then it lowers the entry of every other vertex that has a lighter edge to the new vertex:
best after each town is added. The highlighted towns are in the tree, and their entries add up to .With vertices there are steps, and each step goes through the array once to pick a vertex and once to lower the entries. That is about operations, whatever the number of edges, and no list of edges has to be built. For the 1,000 points of Min Cost to Connect All Points it comes to about operations, while Kruskal's algorithm needed about comparisons for the sort alone:
def min_cost_connect_points(points):
n = len(points)
INF = float("inf")
best = [INF] * n # cheapest connection from each point to the tree
in_tree = [False] * n
best[0] = 0
total = 0
for _ in range(n):
v = -1
for u in range(n): # the closest point that is not in the tree
if not in_tree[u] and (v == -1 or best[u] < best[v]):
v = u
in_tree[v] = True
total += best[v]
for u in range(n): # v may be a cheaper connection for the others
if not in_tree[u]:
cost = abs(points[v][0] - points[u][0]) + abs(points[v][1] - points[u][1])
best[u] = min(best[u], cost)
return total
print(min_cost_connect_points([[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]))
print(min_cost_connect_points([[3, 12], [-2, 5], [-4, 1]]))On 1,000 random points this program took about 0.06 seconds on our machine with Python 3.14, and the program with Kruskal's algorithm about 0.4 seconds.
The array is the better choice when the graph has an edge between most pairs of vertices, as it does here. When the graph has far fewer edges, a version of Prim's algorithm keeps the edges that lead out of the tree in a heap and takes the lightest one from it. That version runs in time. Kruskal's algorithm costs the same and is the shorter program.
Cost of the two algorithms
- Kruskal's algorithm
- Sorting the edges. Each union after that follows at most links.
- Prim's algorithm with the array
- steps, each going through the entries of
best. - Prim's algorithm with a heap
- Each edge is put into the heap at most twice, once from each end.
- Memory
- The edges, and arrays with one entry for each vertex. Prim's algorithm with the array needs only the arrays when the weights can be computed, as they can for the points.
Common minimum spanning tree mistakes
Taking the edges in the order of the input.
- Where it breaks
- With the triangle 0-2 of cost 3, 0-1 of cost 2 and 1-2 of cost 2, given in that order, the loop takes 0-2 and 0-1 for a total of 5. The minimum spanning tree is 0-1 and 1-2, which costs 4.
- The fix
- Sort the edges by cost before the loop.
Stopping Kruskal's loop at the first edge that is skipped.
- Where it breaks
- On the five towns the fourth road, 0-1, is skipped. A loop that stops there has taken three roads of total cost 6, and towns 3 and 4 are not connected to the others.
- The fix
- Skip the edge and go on. The loop may stop once edges have been taken.
Returning the total without checking that the tree reaches every vertex.
- Where it breaks
- With four towns and only the roads 0-1 and 2-3, each of cost 1, Kruskal's algorithm takes both and returns 2, although no road connects town 0 to town 2.
- The fix
- Count the edges taken. Fewer than means the graph is not connected and has no spanning tree.
Recall Does a minimum spanning tree contain the cheapest route between every two vertices?
No. It minimizes the total weight of its edges, which says nothing about a single route. Take a triangle in which the edges 0-1 and 1-2 cost 2 each and the edge 0-2 costs 3. The minimum spanning tree is 0-1 and 1-2, with weight 4, and its route from 0 to 2 costs 4, while the edge 0-2 that it left out costs 3. Cheapest routes are the subject of the Shortest paths lesson, which comes next.