What is a Minimum Spanning Tree?
Learn what a minimum spanning tree is, how Kruskal and Prim algorithms work, and how to answer this graph interview question.
Expected Interview Answer
A minimum spanning tree (MST) is a subset of a connected, weighted, undirected graph's edges that connects every vertex together, contains no cycles, and has the smallest possible total edge weight, and it is found efficiently in O(E log V) time with Kruskal's or Prim's algorithm.
Kruskal's algorithm sorts all edges by weight and greedily adds each one if it does not form a cycle with edges already chosen, using a union-find (disjoint set) structure to detect cycles in near-constant time. Prim's algorithm instead grows a single tree from an arbitrary starting vertex, repeatedly adding the cheapest edge that connects the current tree to a new vertex, typically using a min-heap to find that cheapest edge efficiently. Both are greedy algorithms that provably produce a globally optimal tree because of the cut property: for any partition of vertices, the minimum-weight edge crossing the partition must be in some MST. A spanning tree on n vertices always has exactly n-1 edges, and if any edge weights are equal, multiple valid MSTs can exist with the same total weight.
- Guarantees the cheapest way to connect all nodes with no redundant edges
- Kruskal's algorithm is simple and works well on sparse, edge-heavy input
- Prim's algorithm with a min-heap works well on dense graphs
- Directly used in network design, clustering, and circuit layout
AI Mentor Explanation
A cricket board wants to connect every regional academy to a shared broadcast network at the lowest total cable cost, without building any redundant loops. Kruskal's approach sorts every possible cable link by cost and adds the cheapest one first, skipping any link that would just reconnect two academies already linked through other cables. Prim's approach instead starts from one academy and keeps attaching the cheapest cable that reaches a still-unconnected academy, growing one connected network outward. Either way, the result connects every academy with exactly one fewer cable than there are academies, at the lowest possible total cost.
Step-by-Step Explanation
Step 1
Kruskal's: sort edges
Sort all edges by weight ascending, then process them in that order.
Step 2
Kruskal's: union-find cycle check
Add an edge only if its two endpoints are in different components; merge components with union-find.
Step 3
Prim's: grow from a start vertex
Maintain a min-heap of edges crossing the current tree boundary; always take the cheapest.
Step 4
Stop at n-1 edges
Both algorithms finish once the tree has exactly n-1 edges, connecting all n vertices with minimum total weight.
What Interviewer Expects
- Define MST: connects all vertices, no cycles, minimum total edge weight
- Describe Kruskal's (sort + union-find) and Prim's (grow with min-heap) algorithms
- State the time complexity O(E log V) for both with appropriate data structures
- Explain the cut property as why the greedy choice is provably correct
Common Mistakes
- Forgetting the graph must be connected for a spanning tree to exist at all
- Confusing MST with shortest-path tree (Dijkstra's) — they solve different problems
- Using an array-based cycle check instead of union-find in Kruskal's, hurting performance
- Assuming the MST is unique when edge weights can tie
Best Answer (HR Friendly)
“A minimum spanning tree connects every point in a network using the fewest, cheapest connections possible, with zero redundant loops. I would use it any time I need to design a network — like wiring buildings or laying cable — as cheaply as possible while still keeping everything connected.”
Code Example
class DisjointSet:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]]
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
self.parent[ra] = rb
return True
def kruskal(n, edges):
edges = sorted(edges, key=lambda e: e[2]) # (u, v, weight)
ds = DisjointSet(n)
mst, total = [], 0
for u, v, w in edges:
if ds.union(u, v):
mst.append((u, v, w))
total += w
return mst, totalFollow-up Questions
- How does union-find with path compression improve Kruskal's performance?
- When would you choose Prim's over Kruskal's, or vice versa?
- What is the cut property and how does it prove greedy correctness for MST algorithms?
- How would you find a maximum spanning tree instead of a minimum one?
MCQ Practice
1. How many edges does a minimum spanning tree of a graph with n vertices have?
A spanning tree connecting n vertices with no cycles always has exactly n - 1 edges.
2. What data structure does Kruskal's algorithm use to detect cycles efficiently?
Union-find lets Kruskal's algorithm check in near-constant time whether adding an edge would create a cycle.
3. What is the time complexity of Kruskal's or Prim's MST algorithm using a heap/union-find?
Sorting edges (Kruskal's) or heap operations (Prim's) both give O(E log V) time overall.
Flash Cards
What three properties define a minimum spanning tree? — Connects all vertices, has no cycles, and has minimum total edge weight.
What structure does Kruskal's algorithm use for cycle detection? — Union-find (disjoint set), typically with path compression.
How many edges are in an MST of n vertices? — n - 1.
What property justifies the greedy correctness of MST algorithms? — The cut property: the minimum-weight edge crossing any partition is in some MST.