Minimum Spanning Tree

What is this?

Suppose you have to lay internet cable connecting every house in a town, and every possible stretch of cable has a price. You want every house reachable, but you also want to spend as little as possible — no wasteful extra loops. A Minimum Spanning Tree is the cheapest set of connections that still ties everything together. The recipe is greedy and almost obvious: keep adding the cheapest connection you can, as long as it links up something new instead of forming a pointless loop.

💡 Fun fact: this problem is older than computers. In 1926 the Czech mathematician Otakar Borůvka devised the first minimum-spanning-tree algorithm to solve a very real task — wiring up the electrical grid of Moravia as cheaply as possible. Decades before "computer science" existed, electrification was already a graph problem.

🔓 The problem in this chapter is free. Sign in with Google or Microsoft to start solving.

The one-line idea: given a connected weighted graph, find the cheapest set of edges that keeps everything connected with no cycle — exactly V − 1 edges spanning all V nodes at minimum total weight. Two greedy algorithms both nail it: Kruskal (sort all edges, add the cheapest that doesn't form a cycle, using Union-Find) and Prim (grow one tree outward, always taking the cheapest edge leaving it, using a min-heap).

1. What "minimum spanning tree" really means

A spanning tree touches every vertex using exactly V − 1 edges and contains no cycle (any more edges would create one; any fewer would disconnect it). The minimum spanning tree is the spanning tree of least total edge weight:

Both classic algorithms are greedy, and both are correct because of the cut property: for any way of splitting the vertices into two groups, the single cheapest edge crossing that split is safe to include in some MST. Kruskal and Prim are just two disciplines for repeatedly grabbing safe edges.

⚠️ MST ≠ shortest-path tree. An MST minimizes total edge weight across the whole graph; it does not guarantee the shortest path between any particular pair of nodes. If you need shortest paths from a source, that's Dijkstra, not MST.

2. Where you'll actually meet this

MST is the algorithm of "connect everything as cheaply as possible":

• Network & cable layout. Laying fiber, power lines, or water pipes to reach every site at minimum total cable — the original motivating problem (Borůvka, 1926, for electrifying Moravia).
• Broadcast / multicast trees. Distributing a message to all nodes over a minimum-cost set of links; spanning-tree protocols in switched Ethernet keep the topology loop-free.
• Clustering. Single-linkage hierarchical clustering is literally building an MST and cutting its heaviest edges; removing the k − 1 largest MST edges splits the data into k natural clusters.
• Approximation algorithms. The classic 2-approximation for metric TSP builds an MST and shortcuts a tree walk; MSTs seed many other NP-hard approximations.
• Image processing. Graph-based image segmentation grows regions along low-weight (similar-pixel) MST edges.

If a problem says connect all nodes / minimum cost to link everything / cheapest network — and you don't need pairwise shortest paths — it's an MST.

3. The MST toolkit

1. Kruskal — sort + Union-Find. Sort every edge ascending; scan them, adding an edge only if its endpoints are in different components (Union-Find tells you). Skipping an edge whose endpoints already connect = avoiding a cycle. Great for sparse graphs and pre-sorted edges.
2. Prim — grow with a min-heap. Start at any vertex; repeatedly pull the cheapest edge leaving the current tree to a node not yet in it. Great for dense graphs and when you have an adjacency list.
3. Union-Find done right. Use union by rank/size + path compression so find/union are near-O(1) (inverse-Ackermann). This is what makes Kruskal's post-sort scan nearly linear.
4. Stop at V − 1 edges. A complete MST has exactly V − 1 edges. If you exhaust edges first, the graph was disconnected (you have a spanning forest, not a tree).
5. Lazy heap deletion in Prim. Like Dijkstra, push duplicates on improvement and skip already-in-tree pops (if visited[u]: continue).

The canonical Kruskal implementation (Union-Find + sort):

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:                 # path compression
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False                           # same component -> would make a cycle
        if self.rank[rx] < self.rank[ry]:          # union by rank
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True

def kruskal_mst(n, edges):                          # edges: list of (u, v, weight)
    edges.sort(key=lambda e: e[2])                  # cheapest first
    uf = UnionFind(n)
    mst, total = [], 0
    for u, v, w in edges:
        if uf.union(u, v):                          # connects two components -> safe edge
            mst.append((u, v, w))
            total += w
            if len(mst) == n - 1:                   # tree complete
                break
    return mst, total                               # if len(mst) < n-1: graph was disconnected

4. A 30-second worked example

Kruskal on the graph above. Edges sorted by weight: C-D(1), A-C(2), A-D(3), A-B(4), B-D(5):

Notice A-D(3) is cheaper than A-B(4) yet rejected — adding it would close a cycle since A and D were already connected. Greedy works precisely because Union-Find lets you reject cycle-forming edges in near-constant time.

5. Problems / when to reach for it

• Min Cost to Connect All Points — points with Manhattan-distance edges; build the complete edge set and run Kruskal/Prim. Classic dense-graph MST (Prim shines here).
• Optimize Water Distribution in a Village — model each well as an edge from a virtual "source" node (well cost) plus pipe edges between houses, then MST the whole thing.
• Connecting Cities With Minimum Cost / Min Cost to Connect Sticks — direct MST or greedy-merge variants.
• Reach for MST when you must span all nodes at minimum total cost. Kruskal: O(E log E) (sort-dominated), great when sparse. Prim with a binary heap: O((V + E) log V), great when dense.

6. Common pitfalls 🚫

• Disconnected input. MST requires a connected graph. If Kruskal ends with fewer than V − 1 edges, no spanning tree exists — you got a forest. Decide whether that's an error or the intended answer.
• Cycle detection without Union-Find. Re-running a full reachability check per edge is O(VE)+; Union-Find makes the cycle test near-O(1) — it's the whole point of Kruskal's efficiency.
• Forgetting path compression / union by rank. Without both, Union-Find degenerates toward O(V) per op and Kruskal slows down.
• Confusing MST with shortest paths. The MST path between two nodes is not necessarily their shortest path. Different problem, different algorithm.
• Prim stale-entry handling. Skip heap entries for nodes already in the tree (if visited: continue), or you'll add cycle edges / inflate the count.
• Negative weights are fine. Unlike Dijkstra, MST algorithms handle negative edge weights correctly — the greedy/cut argument doesn't depend on non-negativity.

7. Key takeaways

1. MST = connect all V nodes, no cycle, V − 1 edges, minimum total weight. It minimizes total cost, not pairwise distance.
2. Both algorithms are greedy and correct via the cut property: the cheapest edge crossing any cut is always safe.
3. Kruskal = sort edges + Union-Find (best for sparse / pre-sorted edges); Prim = grow a tree with a min-heap (best for dense graphs).
4. Union-Find with path compression + union by rank is what makes Kruskal near-linear after the sort.
5. MST powers network/cable layout, clustering, broadcast trees, and TSP-style approximations — the go-to whenever "connect everything as cheaply as possible" is the real question.