Minimum Spanning Tree

A minimum spanning tree (MST) is the cheapest set of edges that connects every node of a weighted, undirected, connected graph. Picture islands and a list of bridges you could build, each with a price: you want every island reachable from every other for the lowest total price. It is a network-building problem, not a pathfinding one.

The idea#

Each word in the name is one condition the tree must meet.

Spanning: it includes every vertex.
Tree: it is connected and has no cycles, so with $V$ vertices it has exactly $V - 1$ edges. A cycle would mean paying for a bridge you don't need.
Minimum: among all spanning trees, its total weight is the smallest.

If all edge weights are distinct, the MST is unique.

Two standard algorithms build it. Both are greedy, and they differ in how they pick the next edge:

Kruskal: sort all edges from cheapest to most expensive. Take an edge if it joins two components that aren't connected yet (checked with Union-Find); skip it if it would close a cycle. Stop after $V - 1$ edges.
Prim: start at any node and grow one tree. Keep the edges leaving the tree in a min-heap, pop the cheapest one that reaches a new node, add that node, push its edges, and repeat.

How to spot it#

The cues are about connecting everything at minimum total cost.

"Connect all points / cities / houses with minimum cost."
"Build a network that reaches everyone."
The answer is a total cost, and the chosen edges form $N - 1$ links with no cycles.
"Return -1 if it's impossible to connect everything": the graph may be disconnected.

Template#

Kruskal is usually the one to write in an interview: "pick the cheapest edge, skip it if it makes a cycle" is easy to explain, and it reuses the Union-Find template.

parent = each node is its own root
total = 0; used = 0
for each (w, u, v) in edges sorted by weight:   # cheapest first
    if find(u) == find(v): skip     # would close a cycle
    union(u, v)
    total += w; used += 1
    if used == n - 1: return total  # the tree is complete
return total if n <= 1, else -1     # ran out: disconnected

Prim vs Dijkstra#

Prim's code looks almost identical to Dijkstra's, and the difference is one expression. Dijkstra pushes dist_so_far + weight, because it minimizes the distance from the source. Prim pushes only weight, because it only cares about the cost of connecting the next node to the tree.

	Dijkstra	MST (Prim / Kruskal)
Optimizes	Distance from one source to each node	Total weight to connect all nodes
Result	Shortest-path tree	Spanning tree
Starts from	A specific source	Anywhere; it doesn't matter
Heap key	Cost so far + edge weight	Edge weight only

Complexity and which to choose#

Both are dominated by sorting or heap operations on the edges.

Algorithm	Mechanism	Time	Best for
Kruskal	Sort edges + Union-Find	$O(E \log E)$	Sparse graphs, or edges already given as a list
Prim	Min-heap + visited set	$O(E \log E) = O(E \log V)$	Graphs given as adjacency lists; for very dense graphs, an $O(V^2)$ array version is faster

Prim's heap work is driven by edges, not vertices: each vertex is popped and kept once, but every edge can cause a push. That is why it is $O(E \log E)$ rather than something in terms of $V$ alone.

Pitfalls#

These are the mistakes that most often cost a correct answer.

Using Dijkstra's accumulated cost in Prim. The heap key is the edge weight alone.
In Prim, adding an edge's cost before checking whether its node is already in the tree.
Forgetting the disconnected case: fewer than $V - 1$ edges taken means no spanning tree.
Mixing up 0-based and 1-based node labels.
Running an MST on a directed graph; MST is defined for undirected graphs.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Min Cost to Connect All Points

Every pair of points is a possible edge, weighted by Manhattan distance, so the graph is complete with about $n^2 / 2$ edges. Kruskal builds and sorts all of them. Prim can instead compute distances on the fly from the node it just added, with no stored edge list.

Hint: Connecting Cities With Minimum Cost

The edges are given, and the graph may not be connected. The cities are numbered from 1, so watch the labels. With Prim, return -1 if fewer than $n$ cities end up in the tree; with Kruskal, return -1 if you never reach $n - 1$ edges.

Key takeaways#

An MST connects all $V$ nodes with $V - 1$ edges, no cycles, at the lowest total weight.
Kruskal: sort edges, take each one that joins two different components.
Prim: grow one tree with a heap keyed on edge weight, not distance so far.
Dijkstra minimizes distance from a source; an MST minimizes the cost of connecting everyone.
Both run in $O(E \log E)$ . Both are greedy; see Greedy Overview & Exchange Argument for the exchange-argument view.

Core idea#

A minimum spanning tree (MST) is the cheapest set of edges that connects every node of a weighted, undirected, connected graph. It is a network-building problem, not a pathfinding one.

Key points#

Spanning: every vertex. Tree: connected, no cycles, exactly $V - 1$ edges. Minimum: lowest total weight.
Distinct edge weights give a unique MST.
Kruskal: sort edges cheapest first. Take an edge if Union-Find shows it joins two components.
Prim: grow one tree. Pop the cheapest edge to a new node from a min-heap.
Prim pushes the edge weight only. Dijkstra pushes cost so far plus the weight.
Fewer than $V - 1$ edges taken means the graph is disconnected. Return -1.
Min Cost to Connect All Points is a complete graph. Prim can compute distances on the fly.

Kruskal or Prim#

Algorithm	Mechanism	Time	Best for
Kruskal	Sort + Union-Find	$O(E \log E)$	Sparse graphs, edge lists
Prim	Min-heap + visited	$O(E \log V)$	Adjacency lists; $O(V^2)$ array form for very dense graphs

Template#

parent = each node is its own root
total = 0; used = 0
for each (w, u, v) in edges sorted by weight:
    if find(u) == find(v): skip     # would close a cycle
    union(u, v)
    total += w; used += 1
    if used == n - 1: return total
return total if n <= 1, else -1     # disconnected

Pitfalls#

Using Dijkstra's accumulated cost as Prim's heap key.
In Prim, adding an edge's cost before checking whether its node is already in the tree.
Forgetting the disconnected case.
Mixing up 0-based and 1-based labels.
Running MST on a directed graph.

Say it in an interview#

"Kruskal: cheapest edge first, skip it if Union-Find says it makes a cycle."
"Dijkstra minimizes distance from a source. An MST minimizes the cost to connect everyone."