Minimum Spanning Tree

Connect every node of a weighted graph at the least total cost: Kruskal with Union-Find, Prim with a heap, and the tricks for points in the plane, wells, and critical edges.

Overview

A spanning tree of a connected, undirected graph is a set of edges that joins every node with no cycle. It always has exactly V - 1 edges for V nodes. When the edges have weights, the minimum spanning tree (MST) is the spanning tree with the smallest total weight: the cheapest way to wire every city, house or server together.

This page uses one graph throughout: five nodes and seven weighted edges.

Checking every spanning tree is hopeless: this small graph already has 21. Two greedy algorithms find the MST directly, and both rest on one fact.

Why greedy works

Split the nodes into any two groups (a cut). The lightest edge that crosses the cut belongs to some MST. The reason: any spanning tree must cross the cut somewhere, and if it uses a heavier crossing edge, swapping in the lightest one keeps it a tree and lowers the total. The mirror image is the cycle property: the heaviest edge on any cycle is never needed, because the rest of the cycle already connects its two ends.

Cut property — The lightest edge across any cut is in some MST — Prim (the cut is tree versus not-yet-tree)
Cycle property — The heaviest edge on any cycle is in no MST when weights are distinct — Kruskal (an edge that closes a cycle is skipped)

Both algorithms add edges one at a time, always the cheapest edge that is still safe, and both stop after V - 1 edges.

Kruskal: cheapest edge first

Kruskal sorts the edges by weight, walks them in order, and takes an edge only if its two ends are not yet connected; an edge whose ends are already connected would close a cycle. Union-Find answers 'already connected?' in near-constant time.

The trace on the example graph. Groups are the connected pieces so far.

A-B — 1 — no — take — 1 — AB, C, D, E
C-D — 2 — no — take — 3 — AB, CD, E
A-C — 3 — no — take — 6 — ABCD, E
B-C — 4 — yes — skip — 6 — ABCD, E
B-D — 5 — yes — skip — 6 — ABCD, E
D-E — 6 — no — take — 12 — ABCDE

Four edges are taken (V - 1 for five nodes), so the loop stops without looking at C-E. The MST is A-B, C-D, A-C, D-E with total 12.

The sort costs O(E log E). With path compression and union by rank or size, the E Union-Find calls cost O(E α(V)), where α grows so slowly it is below 5 for any input that fits in memory. So Kruskal is O(E log V): the sort's O(E log E) is the same bound, because E is at most V², and log V² is 2 log V.

Union-Find in four lines

Each node points to a parent, and a node that points to itself is the root of its group. find follows the pointers to the root and, on the way back, points every node it passed straight at the root (path compression). union makes one root point at the other, attaching the smaller tree under the larger (union by size). Two nodes are connected exactly when they have the same root.

find(x) — Returns the root of x's group, flattening the path — Amortized near O(1)
union(x, y) — Joins the two groups if they differ — Amortized near O(1)
connected(x, y) — find(x) == find(y) — Amortized near O(1)

Union-Find is also the answer to 'is the graph connected at all?': if fewer than V - 1 edges are taken, no spanning tree exists and the problem usually wants -1.

Prim: grow one tree

Prim starts from any node and keeps a min-heap of edges that leave the tree. It repeatedly pops the cheapest edge; if it leads to a node already in the tree, discard it, otherwise add that node, add the weight, and push its edges to the heap.

The trace from A. The heap column lists edges as from-to:weight, cheapest first.

A-B — 1 — B is new — take — 1 — AB — A-C:3, B-C:4, B-D:5
A-C — 3 — C is new — take — 4 — ABC — C-D:2, B-C:4, B-D:5, C-E:7
C-D — 2 — D is new — take — 6 — ABCD — B-C:4, B-D:5, D-E:6, C-E:7
B-C — 4 — C already in — discard — 6 — ABCD — B-D:5, D-E:6, C-E:7
B-D — 5 — D already in — discard — 6 — ABCD — D-E:6, C-E:7
D-E — 6 — E is new — take — 12 — ABCDE — C-E:7

Same four edges, same total of 12; only the order they were found in differs. Notice that C-D, weight 2, was taken third even though it is the second-cheapest edge overall: Prim can only take an edge once one of its ends is in the tree.

Every edge is pushed at most twice (once from each end) and popped at most once, so the lazy version is O(E log E), which is O(E log V) because log E is at most 2 log V. A version that keeps one heap entry per node and lowers it in place runs in O((V + E) log V), also O(E log V) on a connected graph, where E is at least V - 1. For a dense graph given as a matrix, a plain array instead of a heap gives O(V²), which beats both when E is near V².

Prim with an array (no heap) — O(V²) — Dense graphs, adjacency matrix, all pairs of points
Prim with a heap (lazy or decrease-key) — O(E log V) — Sparse graphs given as adjacency lists
Kruskal with Union-Find — O(E log V) — Sparse graphs given as an edge list

Kruskal or Prim

Works on — A list of edges — An adjacency list or matrix
Order of work — Cheapest edge anywhere — Cheapest edge leaving the tree
Cycle check — Union-Find — A seen set (node already in the tree)
Time — O(E log V) — O(E log V) with a heap, O(V²) with an array on a dense graph
Disconnected input — Gives a minimum spanning forest; count the edges to notice — Reaches only the start's component
Choose when — The input is an edge list, or edges must be classified — The graph is dense, or the input is a matrix

Both produce the same total. When all weights are distinct, the MST is unique and they produce the same edges; with ties, they may pick different edges with the same total.

Points in the plane

Min Cost to Connect All Points gives coordinates, not edges: any two points may be joined at their Manhattan distance, which is the sum of the horizontal and vertical gaps. Every pair is a possible edge, so n points give n(n - 1) / 2 edges: 6 for 4 points, 45 for 10, 499,500 for 1,000.

(0, 0) to (1, 3) — 1 + 3 = 4
(4, 1) to (5, 4) — 1 + 3 = 4
(0, 0) to (4, 1) — 4 + 1 = 5
(1, 3) to (4, 1) — 3 + 2 = 5
(1, 3) to (5, 4) — 4 + 1 = 5
(0, 0) to (5, 4) — 5 + 4 = 9

Kruskal takes the two 4s, then one of the 5s, for a total of 13. Three different edges of weight 5 finish the tree, so this graph has three MSTs with the same cost; the answer is 13 whichever one you build. Kruskal on all pairs costs O(n² log n) for the sort. Because the graph is complete (dense), Prim with a plain array of best-known distances is O(n²) and needs no edge list at all: keep, for each point outside the tree, the cheapest edge to the tree, and each time a point joins, update the others in O(n).

A virtual node for wells

Optimize Water Distribution gives a cost to dig a well in each house and costs to lay pipes between houses. A well looks like a different kind of choice, but it is an edge in disguise: add one virtual node, the water source, joined to house i by an edge of weight wells[i]. Now every house must be connected to the source, directly (a well) or through pipes, and the cheapest way is the MST of the graph with n + 1 nodes.

1-2 — 1 — take — Pipe between houses 1 and 2
Source-1 — 2 — take — Dig the well in house 1
2-3 — 3 — take — Pipe between houses 2 and 3
Source-3 — 4 — skip — House 3 already has water
Source-2 — 5 — skip — House 2 already has water

Total 6: one well and two pipes.

Critical and pseudo-critical edges

Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree asks you to classify every edge. An edge is critical when removing it makes every spanning tree heavier (or disconnects the graph): it is in every MST. An edge is pseudo-critical when it is in some MST but not in all of them.

MST without e — Heavier than the base MST, or no spanning tree — e is critical
MST forced to start with e — Same weight as the base MST, and e is not critical — e is pseudo-critical
MST forced to start with e — Heavier than the base — e is in no MST

Run Kruskal once for the base weight, then twice per edge (once skipping it, once starting with it taken). That is O(E² α(V)) after one sort. On the graph with edges 0-1 (1), 1-2 (1), 0-2 (2), 2-3 (3), 1-3 (3), the base weight is 5. Skipping either weight-1 edge raises the total to 6, so both are critical. Forcing 0-2 gives 6, so it is in no MST. Forcing 2-3 or 1-3 keeps 5 and skipping either keeps 5 too, so both are pseudo-critical: either can be the tree's third edge.

Variants worth recognizing

Graph may be disconnected — Fewer than V - 1 edges taken; return -1 or the forest, as the problem says
Ties in weights — Several MSTs; the total is the same, the edge set may differ
Maximum spanning tree — Sort descending, or negate the weights
Minimum bottleneck — The MST also minimizes the largest edge used, so no extra work
Clustering into k groups — Build the MST, remove the k - 1 heaviest edges
Directed graph — Not an MST problem; the directed version (minimum arborescence) needs a different algorithm

What you will be able to do

Define a spanning tree and an MST, and say why any MST has exactly V - 1 edges.
Explain in one sentence each why the cut property and the cycle property make greedy choices safe.
Trace Kruskal and Prim on a small graph and give the cost of each.
Turn points, wells and similar inputs into a graph the algorithms accept.
Classify edges as critical or pseudo-critical with two Kruskal runs per edge.

When to use it

The cheapest way to connect every node: cables, roads, pipes (Connecting Cities With Minimum Cost)
Points in the plane that must all be joined (Min Cost to Connect All Points)
A per-node option such as a well that becomes an edge to a virtual node (Optimize Water Distribution)
Which edges every cheapest network must use (Find Critical Edges in MST)
A path whose largest edge is as small as possible (minimum bottleneck), or k clusters from one tree
Any question that says minimum total cost, undirected, every node connected

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio