Minimum Spanning Trees: Two Greedy Algorithms, One Optimal Answer

The cheapest way to connect everything

Given a set of nodes and weighted edges between some of them, a minimum spanning tree (MST) is a subset of edges that connects every node into a single tree -- no cycles, no disconnected pieces -- using the smallest possible total edge weight. It answers a question that shows up constantly in engineering: how do you wire up a power grid, lay pipe, route cable, or connect a set of cities with roads, using the least total material, while still guaranteeing every point is reachable from every other? A spanning tree over n nodes always has exactly n-1 edges -- any fewer and something is disconnected, any more and there is a redundant cycle -- so the MST problem is really about which n-1 edges to keep, out of all the ones available.

Kruskal's algorithm: sort, then greedily add

Kruskal's algorithm (1956) is disarmingly simple: sort every edge in the graph by weight, then walk through them from cheapest to most expensive, adding each edge to the growing forest unless it would create a cycle with edges already added. That single global rule -- always take the cheapest edge that doesn't close a loop -- is enough to guarantee the optimal answer, which is a genuinely surprising fact given how little lookahead the algorithm uses.

sort all edges by weight ascending
for each edge (u, v) in that order:
    if find(u) != find(v):       # u and v are in different components
        union(u, v)               # merge them
        add edge (u, v) to the MST
# stop once n-1 edges have been added

The find/union operations are exactly the Union-Find (disjoint-set) data structure: find(x) reports which component x currently belongs to, and union(u, v) merges two components into one. With the standard optimisations -- union by rank/size and path compression during find -- each operation runs in amortised near-constant time (technically O(alpha(n)), where alpha is the inverse Ackermann function, which is effectively 4 or 5 for any graph size that could ever exist in practice). The dominant cost of Kruskal's algorithm is therefore the initial sort, O(E log E).

Prim's algorithm: grow one tree from a seed

Prim's algorithm (1957, though the core idea traces to Jarnik in 1930) takes a different route to the same optimal answer: start from an arbitrary single node, and repeatedly extend the current tree by adding the cheapest edge that connects a node already in the tree to a node not yet in it. Where Kruskal thinks globally about every edge in the whole graph at once, Prim grows a single connected blob outward, one edge at a time, and never has to worry about accidentally creating a cycle -- by construction, every edge it adds connects a new node, so a cycle is structurally impossible.

start with any single node in the tree
maintain a priority queue of (weight, edge) for every edge leaving the current tree
while the tree has fewer than n nodes:
    pop the cheapest (weight, edge) whose far endpoint is not yet in the tree
    add that edge and its far endpoint to the tree
    push all edges leaving the newly added node

With a binary heap as the priority queue, Prim's algorithm runs in O(E log V); with a Fibonacci heap it improves to O(E + V log V), which matters for very dense graphs. In practice, Prim's tends to be the better choice for dense graphs (many edges relative to nodes), because it never needs to sort edges it will never touch, while Kruskal's tends to be preferred for sparse graphs, since sorting a short edge list is cheap and the Union-Find bookkeeping is minimal.

Why both are guaranteed optimal: the cut property

Both algorithms rely on the same underlying theorem, the cut property: for any way of splitting the graph's nodes into two non-empty groups, the cheapest edge crossing between the two groups is guaranteed to belong to some minimum spanning tree (assuming distinct edge weights, for simplicity). Kruskal exploits this implicitly by always taking the globally cheapest safe edge; Prim exploits it explicitly at every step by choosing the cheapest edge across the specific cut between "nodes already in the tree" and "nodes not yet in the tree." Because every single edge either algorithm adds satisfies the cut property, an inductive argument shows the final set of edges must be a valid MST -- greedy choices, made correctly, chain together into a globally optimal structure, which is unusual; most graph optimisation problems do not permit a purely greedy solution.

Where MSTs show up beyond wiring diagrams

Minimum spanning trees are also the backbone of single-linkage hierarchical clustering: running the algorithm and stopping just before adding the k-1 most expensive edges naturally splits the graph into k clusters, since removing those most-expensive bridging edges is exactly how you'd separate the loosest connections. MSTs are used to approximate solutions to the travelling salesman problem (an MST gives a provable lower bound on the optimal tour, and doubling its edges gives a walkable tour within a factor of two of optimal for metric instances), and they show up in circuit design, network reliability analysis, and image segmentation, where pixel-similarity graphs are cut along their most expensive MST edges to separate regions.

Frequently asked questions

Try it live

Everything above runs in your browser — open Minimum Spanning Tree and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.