AlgoScope

Minimum Spanning Tree

algorithmadvancedTime O(E log V)Space O(V)

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.

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.

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.

Topics covered

Related

Where this is used

NetworkingSpanning Tree Protocol

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.

Machine learningSingle-linkage clustering

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.

Operations researchChristofides in route planners

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.

GamesMaze generation

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