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

Kruskal: sort the 8 edges by weight, 1-2 (1), 1-3 (2), 3-4 (2), 0-2 (3), 0-1 (4), 2-3 (4), 2-5 (5), 4-5 (6), and take each one unless its ends are already connected. Each vertex shows its component; two vertices with the same number are already joined, so an edge between them would close a cycle.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 7, with their answers.

  1. Next cheapest edge is 1-2 (1). Take it or skip it?

    • Take it, joins two components
    • Skip it, would close a cycle

    Answer: Take it, joins two components. Different components, so no cycle: it is the cheapest edge across that cut.

  2. Next cheapest edge is 1-3 (2). Take it or skip it?

    • Take it, joins two components
    • Skip it, would close a cycle

    Answer: Take it, joins two components. Different components, so no cycle: it is the cheapest edge across that cut.

  3. Next cheapest edge is 3-4 (2). Take it or skip it?

    • Take it, joins two components
    • Skip it, would close a cycle

    Answer: Take it, joins two components. Different components, so no cycle: it is the cheapest edge across that cut.

  4. Next cheapest edge is 0-2 (3). Take it or skip it?

    • Take it, joins two components
    • Skip it, would close a cycle

    Answer: Take it, joins two components. Different components, so no cycle: it is the cheapest edge across that cut.

  5. Next cheapest edge is 0-1 (4). Take it or skip it?

    • Take it, joins two components
    • Skip it, would close a cycle

    Answer: Skip it, would close a cycle. Same component: a path between them already exists.

  6. Next cheapest edge is 2-3 (4). Take it or skip it?

    • Take it, joins two components
    • Skip it, would close a cycle

    Answer: Skip it, would close a cycle. Same component: a path between them already exists.

  7. Next cheapest edge is 2-5 (5). Take it or skip it?

    • Take it, joins two components
    • Skip it, would close a cycle

    Answer: Take it, joins two components. Different components, so no cycle: it is the cheapest edge across that cut.

How it runs, step by step

  1. Kruskal: sort the 8 edges by weight, 1-2 (1), 1-3 (2), 3-4 (2), 0-2 (3), 0-1 (4), 2-3 (4), 2-5 (5), 4-5 (6), and take each one unless its ends are already connected. Each vertex shows its component; two vertices with the same number are already joined, so an edge between them would close a cycle.

    Kruskal's algorithm. Edges are considered from cheapest to dearest.

  2. Edge 1-2, weight 1. 1 is in component 1 and 2 in component 2, different, so take it: they merge and the total is 1.

    Edge 1 to 2 weight 1 is taken.

  3. Edge 1-3, weight 2. 1 is in component 2 and 3 in component 3, different, so take it: they merge and the total is 3.

    Edge 1 to 3 weight 2 is taken.

  4. Edge 3-4, weight 2. 3 is in component 3 and 4 in component 4, different, so take it: they merge and the total is 5.

    Edge 3 to 4 weight 2 is taken.

  5. Edge 0-2, weight 3. 0 is in component 0 and 2 in component 4, different, so take it: they merge and the total is 8.

    Edge 0 to 2 weight 3 is taken.

  6. Edge 0-1, weight 4. Both ends are already in component 4, so this edge would close a cycle. Skip it.

    Edge 0 to 1 weight 4 is skipped.

  7. Edge 2-3, weight 4. Both ends are already in component 4, so this edge would close a cycle. Skip it.

    Edge 2 to 3 weight 4 is skipped.

  8. Edge 2-5, weight 5. 2 is in component 4 and 5 in component 5, different, so take it: they merge and the total is 13.

    Edge 2 to 5 weight 5 is taken.

  9. Spanning tree of weight 13 with 5 edges, one fewer than the 6 vertices. Sorting dominates: O(E log E), and each accept is a union-find operation.

    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