Skip to content
wannacode

Minimum spanning tree

In short: A minimum spanning tree connects all vertices of a graph at the lowest total cost; Kruskal's algorithm takes edges by cost and skips every edge that would close a cycle.

Problem

The cheapest network

The delivery company has six offices in the city and wants to connect them with fibre. Every office must reach every other one, directly or through other offices. Digging is expensive: every possible cable has a price in thousands of euros (k€).

List<String> offices = List.of("Centre", "North", "South", "East", "West", "Airport");
List<Cable> cables = List.of(
        new Cable("Centre", "North", 4),
        new Cable("Centre", "South", 6),
        new Cable("Centre", "East", 8),
        new Cable("Centre", "West", 5),
        new Cable("North", "East", 9),
        new Cable("North", "West", 3),
        new Cable("South", "West", 7),
        new Cable("South", "Airport", 11),
        new Cable("East", "Airport", 2));

Laying all nine cables costs 55 k€. But you do not need them all. If three offices are connected in a ring, one cable of the ring is extra: remove it and everything is still connected. The cheapest network has no cycle at all. A connected graph without a cycle is a tree, and a tree with V vertices has exactly V − 1 edges: here 5 cables.

Which five? You are looking for the tree that spans all offices at the lowest total price. That is a minimum spanning tree (MST).

The idea

The cheapest cable that does not close a cycle

Kruskal’s algorithm (Joseph Kruskal, 1956):

  1. Sort the cables by price, cheapest first.
  2. For each cable: if its two ends are not connected yet, lay it. If they are already connected through laid cables, the cable would close a cycle: skip it.
  3. Stop once there are V − 1 cables.

At the start every office is a group of its own. Every laid cable merges two groups into one. The question “are the two ends connected” is exactly the question “are they in one group”, and there is a structure for that: union-find. union(a, b) merges the groups and returns false if a and b are already in one group. One check instead of a search over the map.

See it

Kruskal from the inside

The UnionFind class is the same as in the union-find lesson, unchanged. A cable is a record with two offices and a price, and index turns an office name into a number, because union-find works with numbers.

static List<Cable> kruskal(
        List<String> offices, List<Cable> cables) {
    Map<String, Integer> index = new HashMap<>();
    for (String o : offices) index.put(o, index.size());
    List<Cable> sorted = new ArrayList<>(cables);
    sorted.sort(Comparator.comparingInt(Cable::cost));
    var groups = new UnionFind(offices.size());
    List<Cable> tree = new ArrayList<>();
    for (Cable c : sorted) {
        int a = index.get(c.from());
        int b = index.get(c.to());
        if (!groups.union(a, b)) continue; // a cycle
        tree.add(c);
        if (tree.size() == offices.size() - 1) break;
    }
    return tree;
}
sort with Comparator.comparingInt(Cable::cost) is stable: cables with the same price keep their order.
int total = 0;
for (Cable c : kruskal(offices, cables)) {
    System.out.println(c.from() + " – " + c.to() + ": " + c.cost() + " k€");
    total += c.cost();
}
System.out.println("Total: " + total + " k€");
Output
East – Airport: 2 k€
North – West: 3 k€
Centre – North: 4 k€
Centre – South: 6 k€
Centre – East: 8 k€
Total: 23 k€

static List<Cable> kruskal(
        List<String> offices, List<Cable> cables) {
    Map<String, Integer> index = new HashMap<>();
    for (String o : offices) index.put(o, index.size());
    List<Cable> sorted = new ArrayList<>(cables);
    sorted.sort(Comparator.comparingInt(Cable::cost));
    var groups = new UnionFind(offices.size());
    List<Cable> tree = new ArrayList<>();
    for (Cable c : sorted) {
        int a = index.get(c.from());
        int b = index.get(c.to());
        if (!groups.union(a, b)) continue; // a cycle
        tree.add(c);
        if (tree.size() == offices.size() - 1) break;
    }
    return tree;
}
Step by step, in words
  1. Six offices, nine possible cables, each with a price in thousands of euros. The network has to connect every office as cheaply as possible. On the right the cables get sorted by price: Kruskal looks at them cheapest first. Every office starts as its own group.
  2. East – Airport, 2: different groups. The cable is laid and union merges the two groups into one (same colour).
  3. North – West, 3: different groups again. A second, separate group appears: Kruskal builds several pieces at once, not one tree that grows.
  4. Centre – North, 4: the Centre joins the group of the North and the West.
  5. Centre – West, 5: both ends are already in one group, through the North. This cable would close a cycle: union returns false and the cable is rejected.
  6. Centre – South, 6: the South is alone, so the cable is laid.
  7. South – West, 7: the South and the West are already connected through the Centre. Rejected.
  8. Centre – East, 8: the cheapest cable between the two groups. It merges them, and the cables are now five: six offices, five cables, everything is connected.
  9. The loop stops: North – East and South – Airport are never looked at. Total 23 thousand €, against 55 for all nine cables.

Two groups grow separately: the blue one (East, Airport) and the green one, which starts from North and West. The Centre – East cable is the cheapest between them and merges them. The North – East (9) and South – Airport (11) cables are never looked at.

Try it

Predict the output

The motorway to the airport turns out to be a problem: the East – Airport cable now costs 12. What does the new network cost?

List<Cable> changed = new ArrayList<>(cables);
changed.set(changed.size() - 1, new Cable("East", "Airport", 12));
int total = kruskal(offices, changed).stream().mapToInt(Cable::cost).sum();
System.out.println("Total: " + total + " k€");
Answer

Try it

Fill in

tree.add(c);
if (tree.size() == ) break;

The idea

Why greedy is right here

Kruskal is a greedy algorithm: at every step it takes the best option right now (the cheapest cable that fits) and never goes back. Greedy often lies: see when greedy works and when it fails. Here it works, and the reason is the cut property.

Split the offices into two parts in any way, say the East group and everything else. The cables that run between the two parts are the cut. The cheapest cable in the cut is in the minimum tree. Why? The tree needs at least one cable across the cut, or the two parts are not connected. If that cable is more expensive, swap it for the cheapest one: the network is still connected and the price drops.

Every cable Kruskal lays is the cheapest in the cut between the group of one of its ends and everything else: all cheaper cables have already gone by and sit inside groups. Centre – East (8) is the cheapest of Centre – East, North – East (9) and South – Airport (11), the cables between the two groups.

Try it

Find the bug

A colleague decided union is unnecessary and only asks find whether the two ends are in one group:

static List<Cable> kruskal(
        List<String> offices, List<Cable> cables) {
    Map<String, Integer> index = new HashMap<>();
    for (String o : offices) index.put(o, index.size());
    List<Cable> sorted = new ArrayList<>(cables);
    sorted.sort(Comparator.comparingInt(Cable::cost));
    var groups = new UnionFind(offices.size());
    List<Cable> tree = new ArrayList<>();
    for (Cable c : sorted) {
        int a = index.get(c.from());
        int b = index.get(c.to());
        if (groups.find(a) == groups.find(b)) continue;
        tree.add(c);
        if (tree.size() == offices.size() - 1) break;
    }
    return tree;
}
int total = 0;
for (Cable c : kruskal(offices, cables)) {
    System.out.println(c.from() + " – " + c.to() + ": " + c.cost() + " k€");
    total += c.cost();
}
System.out.println("Total: " + total + " k€");
Output
East – Airport: 2 k€
North – West: 3 k€
Centre – North: 4 k€
Centre – West: 5 k€
Centre – South: 6 k€
Total: 20 k€

20 k€ instead of 23, but East and Airport are cut off, and Centre, North and West form a ring. Which line has the bug?

Pick the line with the bug.

The idea

What it costs

Sorting E cables is O(E log E). After that every check with union-find is almost O(1) (see the union-find lesson). In total O(E log E): the sorting is the expensive part.

Without union-find, “are they connected” is asked with DFS over the cables laid so far:

static boolean connected(Map<String, List<String>> net, String from, String to) {
    Deque<String> stack = new ArrayDeque<>(List.of(from));
    Set<String> seen = new HashSet<>(List.of(from));
    while (!stack.isEmpty()) {
        String office = stack.pop();
        if (office.equals(to)) return true;
        for (String next : net.get(office)) {
            if (seen.add(next)) stack.push(next);
        }
    }
    return false;
}


static List<Cable> kruskalSlow(List<String> offices, List<Cable> cables) {
    Map<String, List<String>> net = new HashMap<>();
    for (String office : offices) net.put(office, new ArrayList<>());
    List<Cable> sorted = new ArrayList<>(cables);
    sorted.sort(Comparator.comparingInt(Cable::cost));
    List<Cable> tree = new ArrayList<>();
    for (Cable c : sorted) {
        if (connected(net, c.from(), c.to())) continue;
        net.get(c.from()).add(c.to());
        net.get(c.to()).add(c.from());
        tree.add(c);
        if (tree.size() == offices.size() - 1) break;
    }
    return tree;
}

The answer is the same. But every search can walk the whole group, O(V), and it runs for every cable: O(E · V).

Run both versions on offices in a grid: each office can be linked to its right and lower neighbour, at a price from 1 to 1000. Every comparison of two prices while sorting is counted, every neighbour looked at by DFS and every step to a parent in find.

  • Kruskal with DFS: a search over the laid cables O(n²)
  • Kruskal with union-find O(n log n)
Algorithmn = 100n = 1,000n = 10,000n = 100,000
Kruskal with DFS: a search over the laid cables4,945677,351≈ 67,735,100≈ 6,773,510,000
Kruskal with union-find1,46023,827321,1713,884,598
The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.
static List<Cable> kruskal(
        List<String> offices, List<Cable> cables) {
    Map<String, Integer> index = new HashMap<>();
    for (String o : offices) index.put(o, index.size());
    List<Cable> sorted = new ArrayList<>(cables);
    sorted.sort(Comparator.comparingInt(Cable::cost));
    var groups = new UnionFind(offices.size());
    List<Cable> tree = new ArrayList<>();
    for (Cable c : sorted) {
        int a = index.get(c.from());
        int b = index.get(c.to());
        if (!groups.union(a, b)) continue; // a cycle
        tree.add(c);
        if (tree.size() == offices.size() - 1) break;
    }
    return tree;
}

At 1000 offices DFS takes 677 351 steps, union-find 23 827. At 100 000 offices union-find makes 3 884 598, and DFS would make billions: Bench does not run them but estimates them from the curve.

The idea

Not the shortest path

In the minimum tree the path from South to Airport is South – Centre – East – Airport: 6 + 8 + 2 = 16. The direct South – Airport cable is 11, but it is not in the network.

A minimum spanning tree saves on the total price of the network. It promises nothing about the path between two offices. If the price is delay and you want the fastest path between two offices, that is a different problem: Dijkstra.

More precisely, if you are curious

Prim is the other classic algorithm for a minimum spanning tree. It starts from one office and each time adds the cheapest cable from the tree to an office outside it. The queue is a priority queue, as in Dijkstra, except the priority is the price of the cable, not the path from the start. With a binary heap it is O(E log V). Kruskal is simpler when the cables are a list, Prim when the graph is given by neighbours and is dense.

If some cables have the same price, there may be several minimum trees, all with the same total price. Kruskal returns one of them, depending on the order of the equal ones.

Where else: power and water networks, roads between villages, circuit boards. If you stop Kruskal before the groups become one (say, at k groups), you get clustering: the points in a group are close, and the groups are far from each other.

Exercise

A cable already laid

Solve it in your editor.

An old cable. There is already a cable between North and East: it costs nothing. Write a method that also takes the laid cables and finds which new ones to add. Print the laid and the new cables and the price of the new ones:

Output
Already laid: North – East
East – Airport: 2 k€
North – West: 3 k€
Centre – North: 4 k€
Centre – South: 6 k€
New cables: 15 k€

Hint: before the loop, merge the ends of the laid cables in union-find. Stop once there is one group.

More tasks

  • The rejected ones. Also print the rejected cables, each with the reason: which cycle it would close.
  • Two networks. The company wants two separate networks. Stop Kruskal when there are two groups. Which offices share a network?
  • Impossible. Remove every cable to the Airport. What does Kruskal return? How do you tell that the network does not connect every office?

Test

Check yourself

1. A network connects 6 offices as cheaply as possible. How many cables does it have?
2. Kruskal reaches a cable whose two ends are already in one group. What does it do?
3. Why does Kruskal use union-find instead of a search (DFS) over the laid cables?
4. In the minimum spanning tree the path from South to Airport goes through Centre and East, 16 k€. The direct South – Airport cable is 11. Does that mean the tree is wrong?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·