What is a Minimum Spanning Tree?
Given a connected, weighted, undirected graph, a minimum spanning tree is a subset of edges that connects every vertex with the smallest possible total weight, without forming any cycle. If the graph has V vertices, the MST has exactly V-1 edges.
MSTs are fundamental in network design. If you need to connect cities with roads, servers with cables, or components on a circuit board, the MST gives you the cheapest way to connect everything.
Kruskal's vs Prim's Algorithm
| Feature | Kruskal's | Prim's |
|---|---|---|
| Approach | Edge-centric (global sort) | Vertex-centric (grow from start) |
| Time complexity | O(E log E) | O(E log V) with binary heap |
| Best for | Sparse graphs | Dense graphs |
| Data structure | Union-Find (disjoint set) | Priority queue (min-heap) |
| Cycle detection | Union-Find: find(u) == find(v) | Implicit: only consider unvisited nodes |
| Edge processing | All edges, sorted by weight | Only frontier edges from visited set |
Kruskal's Algorithm
Sort all edges by weight. Iterate through them in order. For each edge, check if adding it would create a cycle using Union-Find. If not, add it to the MST and merge the two components. Stop when the MST has V-1 edges.
Prim's Algorithm
Start from any vertex. At each step, look at all edges from visited vertices to unvisited vertices. Pick the one with the smallest weight. Add it to the MST and mark the new vertex as visited. Repeat until all vertices are in the MST.
Union-Find (Disjoint Set)
The key data structure for Kruskal's. It supports two operations: find(x) returns the root representative of x's component, and union(x, y) merges two components. With path compression and union by rank, both operations run in nearly O(1) amortized time.
MST in Coding Interviews
MST problems test graph theory and greedy algorithm understanding:
- •Connecting cities with minimum cost — Direct MST application. Model cities as nodes, possible roads as weighted edges.
- •Min cost to connect all points — LeetCode 1584. Compute all pairwise distances, run Kruskal's or Prim's.
- •Critical and pseudo-critical edges — LeetCode 1489. For each edge, check if the MST weight changes when you force-include or force-exclude it.
- •Network delay time variations — Some shortest-path problems have MST components when you need to reach all nodes.
- •Union-Find standalone — Many problems use union-find without MST: number of connected components, redundant connections, accounts merge.
Frequently Asked Questions
What is a minimum spanning tree?add
A minimum spanning tree (MST) of a connected, weighted, undirected graph is a subset of edges that connects all vertices with the minimum possible total edge weight, without forming any cycles. An MST has exactly V-1 edges where V is the number of vertices.
What is the difference between Kruskal's and Prim's algorithm?add
Kruskal's algorithm sorts all edges by weight and adds them one by one if they don't form a cycle, using union-find. Prim's algorithm grows the MST from a starting vertex, always adding the cheapest edge connecting a visited node to an unvisited node. Kruskal's is better for sparse graphs, Prim's for dense graphs.
What is the time complexity of MST algorithms?add
Kruskal's algorithm runs in O(E log E) time due to edge sorting, plus O(E * alpha(V)) for union-find operations which is nearly O(E log E) total. Prim's algorithm runs in O(E log V) with a binary heap or O(V^2) with an adjacency matrix. Both produce the same MST (or one of equal weight if multiple exist).
When are MST algorithms used in practice?add
MSTs are used in network design (minimum cost to connect all locations), clustering (removing the longest edges of an MST gives clusters), image segmentation, and approximation algorithms for NP-hard problems like the traveling salesman problem. They also appear in circuit design and taxonomy.
How does union-find detect cycles in Kruskal's algorithm?add
Union-find (disjoint set) tracks which vertices are in the same connected component. Before adding an edge (u, v), check if find(u) == find(v). If yes, they are already connected, so adding this edge would create a cycle. If no, the edge is safe to add, and union(u, v) merges their components. Path compression and union by rank make this nearly O(1) per operation.