Minimum Spanning Trees

Six villages, A to F, want fibre internet. A trench can be dug between some pairs of villages, and each one has a price. Every village must be able to reach every other one, directly or through other villages. You want to pay as little as possible in total.

This is not a shortest-path problem. You care about the total bill for all the trenches, not how long any one route is.

#The idea: the answer is a tree

Look at any plan that contains a loop. Remove the most expensive cable in that loop. Every village is still connected, because the rest of the loop goes around the gap, and the bill went down. So the cheapest plan never has a loop. A connected set of edges with no loop is a tree, and a tree on V nodes always has exactly V − 1 edges. For six villages, you are looking for five cables.

A tree that reaches every node of a graph is a spanning tree. The cheapest one is the minimum spanning tree, or MST.

Both algorithms in this lesson rest on one rule. Split the villages into any two groups. At least one cable must cross between the groups, or they could not talk. The cheapest cable crossing the split is always safe to take. If some plan used a pricier crossing cable instead, you could swap in the cheapest one and the bill would drop or stay the same.

Here is why the swap always works. Add the cheapest crossing cable to any spanning tree that lacks it. That makes a loop, and the loop must cross the split a second time through another cable that costs at least as much. Remove that one. You still have a spanning tree, and it is no more expensive.

#Kruskal: cheapest cables first

Sort every possible cable by price. Walk down the list. Take a cable if its two villages are not connected yet. Skip it if they already are, because it would only close a loop. Stop once you have V − 1 cables.

"Are these two already connected?" while groups keep merging is exactly the question Union-Find answers. union(u, v) returns false when u and v already share a root, which is your signal to skip.

sort cables by costfor each cable (u, v) in that order:  if find(u) == find(v): skip (would close a loop)  else: union(u, v), take the cable  stop when you have V − 1 cables

Each cable Kruskal takes is safe by the rule above. Split the villages into "the group at one end of the cable" and "everything else". Every cheaper cable was already taken or skipped, so it lies inside a group and does not cross this split. The cable in hand is the cheapest that does.

// n villages numbered 0..n-1. edges: list of [cost, u, v].
// UnionFind: the class from the union-find lesson.
function kruskal(n, edges) {
  const sorted = [...edges].sort((a, b) => a[0] - b[0]); // cheapest first
  const uf = new UnionFind(n);
  const chosen = [];
  let total = 0;
  for (const [cost, u, v] of sorted) {
    if (uf.union(u, v)) { // false means u and v were already connected
      chosen.push([u, v, cost]);
      total += cost;
      if (chosen.length === n - 1) break; // a spanning tree has n - 1 edges
    }
  }
  return chosen.length === n - 1 ? { total, chosen } : null; // null: not connected
}

# n villages numbered 0..n-1. edges: list of (cost, u, v).
# UnionFind: the class from the union-find lesson.
def kruskal(n, edges):
    uf = UnionFind(n)
    chosen = []
    total = 0
    for cost, u, v in sorted(edges):  # cheapest first
        if uf.union(u, v):  # False means u and v were already connected
            chosen.append((u, v, cost))
            total += cost
            if len(chosen) == n - 1:  # a spanning tree has n - 1 edges
                break
    return (total, chosen) if len(chosen) == n - 1 else None  # None: not connected

#Prim: grow one tree outward

Prim's algorithm starts at any village and grows a single tree. At each step it takes the cheapest cable that leaves the tree, which is the cheapest cable crossing the split "in the tree" versus "not yet". A min-heap keeps those cables ready, just as in Dijkstra's algorithm. Cables that point back into the tree become stale and get skipped.

add start to the tree; push its cableswhile the tree is missing villages:  pop the cheapest cable (cost, v)  if v is already in the tree: skip  add v to the tree; total += cost  push v's cables to villages not in the tree

// graph: adjacency list, graph[u] = list of [v, cost]. Villages 0..n-1.
// heapPush / heapPop: the pair heap used in the Dijkstra lesson.
function prim(graph, start = 0) {
  const inTree = new Set();
  const heap = [[0, start]]; // [cost of the cable that reaches node, node]
  let total = 0;
  while (heap.length > 0 && inTree.size < graph.length) {
    const [cost, node] = heapPop(heap);
    if (inTree.has(node)) continue; // already joined by a cheaper cable
    inTree.add(node);
    total += cost;
    for (const [next, cableCost] of graph[node]) {
      if (!inTree.has(next)) heapPush(heap, [cableCost, next]);
    }
  }
  return inTree.size === graph.length ? total : null; // null: not connected
}

import heapq
 
# graph: adjacency list, graph[u] = list of (v, cost). Villages 0..n-1.
def prim(graph, start=0):
    in_tree = set()
    heap = [(0, start)]  # (cost of the cable that reaches node, node)
    total = 0
    while heap and len(in_tree) < len(graph):
        cost, node = heapq.heappop(heap)
        if node in in_tree:
            continue  # already joined by a cheaper cable
        in_tree.add(node)
        total += cost
        for nxt, cable_cost in graph[node]:
            if nxt not in in_tree:
                heapq.heappush(heap, (cable_cost, nxt))
    return total if len(in_tree) == len(graph) else None  # None: not connected

Put the code next to Dijkstra's and only one thing really differs: the number pushed onto the heap. Dijkstra pushes d + cost, the whole trip from the start. Prim pushes just cost, the price of the one cable. Dijkstra asks "how far is this from home?"; Prim asks "how cheap is it to hook this on?".

Pick Kruskal when the input is a plain list of edges, and Prim when you already have an adjacency list.

#Common mistakes

#Check yourself

#What to practise next

Kruskal and Prim are both greedy: each takes the cheapest safe step and never looks back, and the cut rule proves that never goes wrong. Greedy Algorithms shows when that kind of shortcut works, and how to spot when it does not.