AlgoScope

Minimum Spanning Tree

A spanning tree connects every vertex with the fewest possible edges, and a minimum one does it at the lowest total weight. Both classic algorithms lean on one fact: split the vertices into two groups any way you like, and the cheapest edge crossing the split belongs in some minimum spanning tree. Kruskal walks the edges from cheapest to dearest and keeps each one that joins two separate components. Prim grows a single tree from a start vertex and always takes the cheapest edge leaving it. Boruvka is the third classic and the oldest: every component picks its cheapest edge to the outside and all the picks are added in one round, so the number of components at least halves each time. It needs no sort and no priority queue, and because every pick is independent it is the algorithm of choice on parallel hardware.

The player

Boruvka's algorithm over 6 vertices and 8 edges.43124265001122334455

Boruvka: every vertex starts as its own component, shown by the number on it. In each round every component looks at its cheapest edge to the outside and all of those edges are added at once, so the number of components at least halves per round. Where Kruskal takes one edge at a time and Prim grows one tree, Boruvka grows all the trees in parallel, which is why it is the one used on parallel machines.

Check your understanding

The player pauses before the one decision in this run and asks what happens next. Here it is, with the answer.

  1. 6 components each pick a cheapest outgoing edge. How many components can remain after this round?

    • At most 3: every component merges with at least one other
    • Exactly 5: one merge per round
    • Still 6 until the next round

    Answer: At most 3: every component merges with at least one other. Every component joins at least one other, so the count at least halves each round: at most log2 n rounds.

How it runs, step by step

  1. Boruvka: every vertex starts as its own component, shown by the number on it. In each round every component looks at its cheapest edge to the outside and all of those edges are added at once, so the number of components at least halves per round. Where Kruskal takes one edge at a time and Prim grows one tree, Boruvka grows all the trees in parallel, which is why it is the one used on parallel machines.

    Boruvka's algorithm over 6 vertices and 8 edges.

  2. Round 1: 6 components. Each picks its cheapest edge to another component: component 0 picks 0-2 (3), component 1 picks 1-2 (1), component 2 picks 1-2 (1), component 3 picks 1-3 (2), component 4 picks 3-4 (2), component 5 picks 2-5 (5). 5 distinct edges, because two components often pick the same one.

    Round 1: 5 edges picked by 6 components.

  3. Add all 5 picked edges at once: 1-2, 1-3, 3-4, 0-2, 2-5. 6 components become 1, total weight 13. A picked edge is the cheapest edge leaving its component, so by the cut property it belongs to the minimum spanning tree, and the ordering tie-break keeps two picks from ever closing a cycle.

    1 components left, total 13.

  4. Spanning tree of weight 13 with 5 edges after 1 round. Each round scans every edge once, O(E), and there are at most log2 n rounds: O(E log V) with no priority queue and no sort, and every component's pick is independent of the others, which is what a parallel machine wants.

    Total weight 13 with 5 edges.

The code

Minimum Spanning Tree, in Python

def kruskal(n, edges):
    parent = list(range(n))
    def find(x):
        if parent[x] == x:
            return x
        parent[x] = find(parent[x])
        return parent[x]
    total = 0
    for u, v, w in sorted(edges, key=lambda e: e[2]):      # cheapest first
        a = find(u)
        b = find(v)
        if a == b:
            continue                                       # same component: a cycle
        parent[a] = b
        total += w                                         # union
    return total

def prim(adj, start):
    in_tree = [False] * len(adj)
    in_tree[start] = True
    total = 0
    for _ in range(len(adj) - 1):
        best = None
        for u in range(len(adj)):
            if in_tree[u]:
                for v, w in adj[u]:
                    if not in_tree[v] and (best is None or w < best[2]):
                        best = (u, v, w)                   # cheapest
        if best is None:
            return total                                   # disconnected: no more crossing edges
        _, v, w = best
        in_tree[v] = True
        total += w
    return total

def boruvka(n, edges):
    parent = list(range(n))
    total = 0
    components = n
    def find(x):
        if parent[x] == x:
            return x
        parent[x] = find(parent[x])
        return parent[x]
    while components > 1:                                  # each round at least halves them
        cheapest = [None] * n                              # per component: its cheapest way out
        for e in edges:
            a, b = find(e[0]), find(e[1])
            if a == b:
                continue                                   # inside one component: useless
            if cheapest[a] is None or e[2] < cheapest[a][2]:
                cheapest[a] = e
            if cheapest[b] is None or e[2] < cheapest[b][2]:
                cheapest[b] = e
        for e in dict.fromkeys(p for p in cheapest if p is not None):   # add every pick, all at once
            a, b = find(e[0]), find(e[1])
            if a != b:
                parent[a] = b
                total += e[2]
                components -= 1
    return total

Minimum Spanning Tree, in JavaScript

function kruskal(n, edges) {
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x])));
  let total = 0;
  for (const [u, v, w] of [...edges].sort((e, f) => e[2] - f[2])) { // cheapest first
    const a = find(u); const b = find(v);
    if (a === b) continue;                                          // same component: a cycle
    parent[a] = b; total += w;                                      // union
  }
  return total;
}

function prim(adj, start) {
  const inTree = new Array(adj.length).fill(false);
  inTree[start] = true;
  let total = 0;
  for (let round = 0; round < adj.length - 1; round++) {
    let best = null;
    for (let u = 0; u < adj.length; u++) if (inTree[u]) for (const [v, w] of adj[u]) {
      if (!inTree[v] && (best === null || w < best[2])) best = [u, v, w];   // cheapest
    }
    if (best === null) return total;                                        // disconnected: no more crossing edges
    const [, v, w] = best;
    inTree[v] = true; total += w;
  }
  return total;
}

function boruvka(n, edges) {
  const parent = Array.from({ length: n }, (_, i) => i);
  let total = 0;
  let components = n;
  const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x])));
  while (components > 1) {                                          // each round at least halves them
    const cheapest = new Array(n).fill(null);                       // per component: its cheapest way out
    for (const e of edges) {
      const a = find(e[0]); const b = find(e[1]);
      if (a === b) continue;                                        // inside one component: useless
      if (cheapest[a] === null || e[2] < cheapest[a][2]) cheapest[a] = e;
      if (cheapest[b] === null || e[2] < cheapest[b][2]) cheapest[b] = e;
    }
    for (const e of new Set(cheapest.filter((p) => p !== null))) {  // add every pick, all at once
      const a = find(e[0]); const b = find(e[1]);
      if (a !== b) { parent[a] = b; total += e[2]; components--; }
    }
  }
  return total;
}

Minimum Spanning Tree, in Kotlin

fun kruskal(n: Int, edges: List<Triple<Int, Int, Int>>): Int {
    val parent = IntArray(n) { it }
    fun find(x: Int): Int = if (parent[x] == x) x else find(parent[x]).also { parent[x] = it }
    var total = 0
    for ((u, v, w) in edges.sortedBy { it.third }) {         // cheapest first
        val a = find(u); val b = find(v)
        if (a == b) continue                                   // same component: a cycle
        parent[a] = b; total += w                              // union
    }
    return total
}

fun prim(adj: List<List<Pair<Int, Int>>>, start: Int): Int {
    val inTree = BooleanArray(adj.size).also { it[start] = true }
    var total = 0
    repeat(adj.size - 1) {
        var best: Triple<Int, Int, Int>? = null
        for (u in adj.indices) if (inTree[u]) for ((v, w) in adj[u]) {
            if (!inTree[v] && (best == null || w < best.third)) best = Triple(u, v, w)   // cheapest
        }
        val (_, v, w) = best ?: return total                    // disconnected: no more crossing edges
        inTree[v] = true; total += w
    }
    return total
}

fun boruvka(n: Int, edges: List<Triple<Int, Int, Int>>): Int {
    val parent = IntArray(n) { it }; var total = 0; var components = n
    fun find(x: Int): Int = if (parent[x] == x) x else find(parent[x]).also { parent[x] = it }
    while (components > 1) {                                   // each round at least halves them
        val cheapest = arrayOfNulls<Triple<Int, Int, Int>>(n)   // per component: its cheapest way out
        for (e in edges) {
            val (a, b) = find(e.first) to find(e.second)
            if (a == b) continue                                   // inside one component: useless
            if (cheapest[a] == null || e.third < cheapest[a]!!.third) cheapest[a] = e
            if (cheapest[b] == null || e.third < cheapest[b]!!.third) cheapest[b] = e
        }
        for (e in cheapest.filterNotNull().distinct()) {        // add every pick, all at once
            val (a, b) = find(e.first) to find(e.second)
            if (a != b) { parent[a] = b; total += e.third; components-- }
        }
    }
    return total
}

This lesson has no write-it-yourself editor. It is free, like every lesson, and nothing here is locked.

Remember

  • Cut property: the cheapest edge across any split of the vertices is safe to take.
  • Kruskal: sort edges, take one unless its ends are already connected. Union-find answers that.
  • Prim: grow one tree, always adding the cheapest edge with exactly one end inside it.

Where this is used

Spanning Tree ProtocolNetworking

Ethernet frames carry no hop count, so one loop between switches floods the segment forever. IEEE 802.1D has the switches elect a root bridge, and every other switch then keeps only its lowest-cost path back to that root and blocks its remaining ports. What is left is a spanning tree of the switch topology with exactly one path between any two switches, so a frame has nowhere to circle. Note what it is not: the tree is chosen by each switch's cost to the root, which makes it a shortest-path tree rather than the minimum-weight tree Kruskal or Prim would build over the same links. When a link fails the switches recompute and unblock a port that was standing by.

Single-linkage clusteringMachine learning

Single-linkage clustering is Kruskal with the merge order kept: build the minimum spanning tree over the distance graph and cutting its heaviest edges splits the points into clusters. scikit-learn's HDBSCAN does exactly that over a mutual-reachability distance, then reads the cluster hierarchy off the order the edges were added. The spanning tree is what makes it tractable, since the full distance graph has n squared edges but only n - 1 of them ever decide anything.

Christofides in route plannersOperations research

A minimum spanning tree is a lower bound on the best travelling salesman tour, because deleting any one edge from a tour leaves a spanning path, which is itself a spanning tree. Christofides' approximation builds on that: take the MST, add a minimum-weight perfect matching on its odd-degree vertices, and shortcut the Euler tour that results. On inputs obeying the triangle inequality that lands within 1.5 times optimal. Google OR-Tools offers CHRISTOFIDES as a first-solution strategy for its routing solver, though its version uses a maximal matching rather than the minimum-weight one and gives up the 1.5 guarantee for speed. Either way the MST is what the local search starts improving from.

Maze generationGames

A perfect maze, one with exactly one route between any two cells, is a spanning tree of the grid graph: no cycles means no loops to wander, connected means no walled-off region. Give every wall a random weight and run Kruskal or Prim over it and you get one for free. Picking one algorithm over the other does not change the maze, though: with distinct weights the minimum spanning tree is unique, so both carve the same corridors and only the order of carving differs. The variant people call randomized Prim is a different rule, taking a random wall off the frontier instead of the cheapest, and that is where the change in texture comes from.

Why it works this way

Why is greedy safe here when it fails almost everywhere else?

The cut property is not obvious, it is proved by exchange. Suppose e is the cheapest edge crossing some split and a minimum spanning tree T leaves it out: adding e to T creates exactly one cycle, and that cycle has to cross the split a second time on some edge f, which by assumption is no cheaper than e. Swap f out for e and you have another spanning tree of no greater weight, so taking e cost you nothing. Kruskal's split is the component of the edge's endpoint against everything else, Prim's split is the tree against the rest, and that is the whole reason both are allowed to be greedy.

Ties are where Boruvka breaks

If every weight is distinct the minimum spanning tree is unique and each component's cheapest way out is unambiguous. Add ties and two components can each name a different edge of the same weight between them, or a ring of components can each pick into the next, so adding every pick in one round closes a cycle. Two standard fixes: break ties by a total order such as weight then edge index so no two edges are ever equal, or re-check find on both ends immediately before each union, which is what the loop above does with its second find.

Prim and Dijkstra differ by one term

Both grow a set outward from a start vertex and both take the cheapest frontier item next. The only difference is what cheapest means: Prim keys a vertex by w, the weight of the single edge reaching it, while Dijkstra keys it by dist[u] + w, the cost of the whole route from the source. That one term is why a minimum spanning tree is not a shortest-path tree - the path between two vertices along the MST can be far longer than their actual shortest path. Prim when you want the cheapest network overall, Dijkstra when you want the cheapest trip from one place.

Kruskal needs union-find, not a visited flag

Are these two vertices already connected is not a local question the way have I seen this vertex is, so a boolean array cannot answer it. Without union-find you would re-run a traversal for every candidate edge and Kruskal becomes O(E * V). With it each check is near constant, so the cost collapses back onto the sort. The classic bug in the union step is writing parent[u] = v with the original vertices instead of the roots: that re-parents a node which already had a parent and detaches part of a component from it. Nothing crashes in the usual case, the totals just come back wrong.

Read more

Next up

Plane Geometry

Points, a vector and a distance

Next lesson: Plane Geometry