Graphs · pattern 8 of 8

Minimum spanning tree

A minimum spanning tree is the cheapest set of links that joins all the places into one piece. Grow it from any place: again and again, add the cheapest link that leads from the tree to a place outside it.

Watch it run in the app

When to use it

Use it when you choose which links to build so that everything is joined at the lowest total cost, and no single route has to be short.

It belongs to the graphs group: Visit every place you can reach, once each, in the order that suits the question.

Watch it work

An office has 5 rooms, numbered 0 to 4. A cable can be laid between some pairs of rooms, and [a, b, price] gives the price of one such cable. Return the lowest total price of cables that join all the rooms into one network.

Input
n = 5
cables = [[0, 1, 4], [0, 2, 3], [1, 2, 2], [1, 3, 6], [2, 3, 5], [2, 4, 7], [3, 4, 1]]

Output
11

The method

List the cables that can leave each room
Give each room a cost to join the tree; room 0 costs 0
Find the room outside the tree that is cheapest to join
Add that room to the tree and its cost to the total
A cable from the new room may be cheaper: lower the costs
Every room is in the tree: return the total

The run, one moment at a time

Step 1. The office has 5 rooms and 7 possible cables, each marked with its price. Choose cables so that every room is joined and the total price is as low as it can be.
```
cost: ∞ ∞ ∞ ∞ ∞
total: 0
```
Step 2. The tree will grow from room 0, so room 0 costs 0 to join. No cable to the other rooms is known yet, so their costs are ∞.
```
cost: 0 ∞ ∞ ∞ ∞
total: 0
```
Step 4. Room 0 is the only room with a known cost, so it joins first. The tree is one room, and the total is still 0.
```
cost: 0 ∞ ∞ ∞ ∞
total: 0
```
Step 5. Cables from room 0: room 1 for 4; room 2 for 3. Both beat ∞, so these are their costs to join now.
```
cost: 0 4 3 ∞ ∞
total: 0
```
Step 3. Outside the tree, room 1 costs 4 and room 2 costs 3. No cable from the tree reaches rooms 3 and 4 yet. Room 2 is the cheapest to join.
```
cost: 0 4 3 ∞ ∞
total: 0
```
Step 4. Add room 2 by its cable from room 0. The total is 0 + 3 = 3.
```
cost: 0 4 3 ∞ ∞
total: 3
```
Step 5. Cables from room 2: room 1 for 2, which beats 4; room 3 for 5; room 4 for 7. Only the price of the one cable counts, not the way back to room 0.
```
cost: 0 2 3 5 7
total: 3
```
Step 4. Room 1 is the cheapest room outside now, at 2. Add it: 3 + 2 = 5. Its cable to room 3 costs 6, which does not beat 5, so no cost changes.
```
cost: 0 2 3 5 7
total: 5
```
Step 4. Room 3 is the cheapest room outside now, at 5. Add it: 5 + 5 = 10.
```
cost: 0 2 3 5 7
total: 10
```
Step 5. Cables from room 3: room 4 for 1, which beats 7. Lower the cost of room 4 to 1.
```
cost: 0 2 3 5 1
total: 10
```
Step 4. Room 4 is the last room outside, at 1. Add it: 10 + 1 = 11. Every room is in the tree.
```
cost: 0 2 3 5 1
total: 11
```
Step 6. All 5 rooms are joined by 4 cables for a total of 11. The 3 cables left out are not needed: each of them would close a loop.
```
cost: 0 2 3 5 1
total: 11
```

The code

The numbered comments are the steps of the method.

JavaScript

function solve(n, cables) {
  // 1. List the cables that can leave each room
  const graph = Array.from({ length: n }, () => []);
  for (const [a, b, price] of cables) {
    graph[a].push([b, price]);
    graph[b].push([a, price]);
  }
  // 2. Give each room a cost to join the tree; room 0 costs 0
  const cost = Array(n).fill(Infinity);
  cost[0] = 0;
  const used = Array(n).fill(false);
  let total = 0;
  for (let round = 0; round < n; round++) {
    // 3. Find the room outside the tree that is cheapest to join
    let nearest = -1;
    for (let room = 0; room < n; room++) {
      if (used[room]) continue;
      if (nearest < 0 || cost[room] < cost[nearest]) nearest = room;
    }
    // 4. Add that room to the tree and its cost to the total
    used[nearest] = true;
    total += cost[nearest];
    // 5. A cable from the new room may be cheaper: lower the costs
    for (const [other, price] of graph[nearest]) {
      if (!used[other] && price < cost[other]) cost[other] = price;
    }
  }
  // 6. Every room is in the tree: return the total
  return total;
}

Python

def solve(n, cables):
    # 1. List the cables that can leave each room
    graph = [[] for _ in range(n)]
    for a, b, price in cables:
        graph[a].append((b, price))
        graph[b].append((a, price))
    # 2. Give each room a cost to join the tree; room 0 costs 0
    cost = [float("inf")] * n
    cost[0] = 0
    used = [False] * n
    total = 0
    for _ in range(n):
        # 3. Find the room outside the tree that is cheapest to join
        nearest = -1
        for room in range(n):
            if used[room]:
                continue
            if nearest < 0 or cost[room] < cost[nearest]:
                nearest = room
        # 4. Add that room to the tree and its cost to the total
        used[nearest] = True
        total += cost[nearest]
        # 5. A cable from the new room may be cheaper: lower the costs
        for other, price in graph[nearest]:
            if not used[other] and price < cost[other]:
                cost[other] = price
    # 6. Every room is in the tree: return the total
    return total

How to spot it

Asked: Connect all the points at the lowest total cost: The cheapest way to join everything has no closed loop, so it is a tree that reaches every point: n points, n - 1 links.
Given: A list of possible links, each with a cost: You decide which links to build. Grow one tree, and always add the cheapest link that reaches a point outside it.
Limits: Up to 1,000 points, and any two of them may be linked: That is about 500,000 possible links, far too many to try in sets. Growing the tree takes about 2 million steps.

Looks like it, but is not

You need the cheapest route from one place to another. Use Weighted shortest path. A route's cost is counted from its start. The tree compares one link at a time, and its way between two places may be a long one.
The links have no costs, and you only need to know which places are joined. Use Union-find. With no costs there is nothing to make cheapest. Merging groups link by link shows which places are together.
Only the k cheapest links are wanted, whether or not they join everything. Use Heap of the best k. That keeps the k smallest costs and nothing else. A tree must also reach every place, so a cheap link can be useless.

Cost and mistakes

Each of the n rounds scans all n rooms for the cheapest one, so this method, Prim's algorithm, takes about n × n steps, O(n²), plus two looks at each cable. Extra space is the cable lists and one cost for each room.

Watch out

Compare the price of one cable, not the price of the whole way back to the first room. Adding prices along the way is the shortest-path method, and it can choose other cables.
If some place cannot be reached at all, its cost stays unknown and no tree exists. Test for that before you add the cost to the total.

In the 150

One problem of the 150 uses it. Naming them gives their method away, so the list is folded.

Show it

Min Cost to Connect All PointsMedium · Advanced Graphs