Existence
Every connected undirected graph has at least one MST.
Algorithms · Weighted graphs
Minimum spanning tree
Given a connected, undirected, weighted graph, a minimum spanning tree connects all vertices without cycles while minimizing the sum of edge weights.
Three constraints, one objective
T = (V, ET) must be spanning, connected and acyclic, with |ET| = |V| − 1.
w(T) = Σe∈ET w(e) → min
“Minimum” refers to total weight, not edge count: every spanning tree already has exactly |V| − 1 edges. A disconnected graph has no single MST, but it does have a minimum spanning forest.
Uniqueness
Distinct edge weights guarantee a unique MST; equal weights may yield several optima.
Negative weights
They are allowed: cycles cannot be repeated because the solution is a tree.
The properties that make greedy choices safe
The lightest crossing edge
For any cut respecting already selected edges, a minimum-weight crossing edge is safe for some MST. This justifies both Prim and Kruskal.
The heaviest may be excluded
In a cycle, an edge strictly heavier than all others belongs to no MST: removing it preserves connectivity at lower cost.
Prim vs Kruskal
| Aspect | Prim | Kruskal |
|---|---|---|
| Growth | One tree from a source | A forest whose components merge |
| Greedy choice | Lightest edge from tree to outside | Globally lightest edge that creates no cycle |
| Key structure | Priority queue | Disjoint Set Union |
| Often preferable | Dense graphs or adjacency-based input | Sparse graphs already stored as edge lists |
Lab: build the MST
Compare both algorithms on the same graph. Green edges are accepted, the orange edge is under inspection and red edges are rejected because they would close a cycle.
Syntax: A-B:4, A-C:3 · 2 to 10 vertices, at most 24 edges.
Examples
Edges crossing the cut
Selected edges
Vertices in the tree
Current cost
0
- Accepted edges
- 0
- Examined edges
- 0
- Components
- —
- Total cost
- 0
Why Prim and Kruskal are correct
Both maintain an edge set A contained in some MST. Prim uses the cut between reached and unreached vertices; Kruskal uses a cut separating the candidate edge’s two components. In either case, the lightest crossing edge is safe. By induction, after |V| − 1 choices A is a minimum spanning tree.
Complexity analysis
| Implementation | Time | Auxiliary space | Note |
|---|---|---|---|
| Prim · matrix + scan | Θ(|V|²) | Θ(|V|) | Good for dense graphs. |
| Prim · lists + binary heap | O(|E| log |V|) | O(|V| + |E|) | Priority queue handles each update. |
| Kruskal · sort + DSU | O(|E| log |E|) | O(|V| + |E|) | Sorting dominates; log |E| = O(log |V|) in simple graphs. |
With union by rank and path compression, DSU operations take amortized O(α(|V|)), effectively constant. The visualizer uses explicit scans to expose every candidate; the table describes efficient implementations.
Applications and limits
Physical networks
Preliminary design of cables, pipes or roads at minimum total cost.
Clustering
Removing the heaviest MST edges separates distant groups.
Approximations
MSTs appear in metric TSP heuristics and network approximations.
MST ≠ shortest path. An MST minimizes the whole network’s cost; a shortest-path tree minimizes distances from one source. They are generally different structures.
Common mistakes and exercises
- Using Prim on directed edges without changing the model: the classical MST is defined for undirected graphs.
- In Kruskal, accepting an edge merely because it is light without checking whether it joins different components.
- Concluding that the MST is unique when equal weights exist.
On the classic graph, predict cost and edges before running both algorithms.
Change Prim’s source: does the cost change? What about selected edges with ties?
Try the disconnected graph and explain why the result is a forest, not an MST.