What is Kruskal's Algorithm?
Learn how Kruskal's algorithm builds a minimum spanning tree using sorted edges and union-find, with code and a full answer.
Expected Interview Answer
Kruskal's algorithm builds a minimum spanning tree by sorting all edges by weight ascending and greedily adding each edge that connects two previously disconnected components, using a union-find (disjoint-set) structure to reject edges that would create a cycle.
After sorting the E edges in O(E log E) time, the algorithm walks them from lightest to heaviest and, for each edge (u, v), checks whether u and v already belong to the same set via a find operation; if they do, adding the edge would create a cycle so it is skipped, and if they don't, the edge is added to the spanning tree and the two sets are merged via a union operation. The process stops once V-1 edges have been added, guaranteeing a tree that connects all vertices with the minimum possible total edge weight. With union-find optimized by path compression and union by rank, each find/union runs in nearly O(1) amortized time, making the sort the dominant cost at O(E log E). Kruskal's is the natural choice when the edge list is already available or the graph is sparse, whereas Prim's is often preferred for dense graphs with an adjacency matrix.
- Produces a provably minimum-weight spanning tree
- Simple greedy rule: cheapest edge that avoids a cycle
- Union-find makes cycle checks nearly O(1) amortized
- Works well on sparse graphs given as an edge list
AI Mentor Explanation
A board wants to link every regional cricket academy with the cheapest possible set of training-exchange partnerships, so it sorts every candidate partnership by cost from cheapest to priciest. It then adds partnerships one by one, skipping any that would just re-link academies already connected through earlier partnerships — that would be a wasted, cycle-forming deal. Each accepted partnership merges two previously separate academy clusters into one connected group, tracked with a quick lookup of which cluster each academy belongs to. Once enough partnerships connect every academy into a single network, the board stops, having spent the minimum possible total cost while avoiding any redundant, cycle-creating links.
Step-by-Step Explanation
Step 1
Sort all edges by weight
Sort the E edges ascending by weight in O(E log E) time.
Step 2
Initialize union-find
Each vertex starts as its own singleton set for cycle detection.
Step 3
Greedily add edges
For each edge in sorted order, add it if its two endpoints are in different sets (find), then union those sets.
Step 4
Stop at V-1 edges
Once V-1 edges are accepted, all vertices are connected with minimum total weight.
What Interviewer Expects
- Explain the greedy rule: cheapest edge that does not form a cycle
- Describe union-find (disjoint-set) and why it detects cycles efficiently
- State O(E log E) time, dominated by the sort
- Contrast with Prim's algorithm and when each is preferred
Common Mistakes
- Forgetting to check for cycles, producing an invalid spanning structure
- Using a naive cycle check (like DFS per edge) instead of union-find, blowing up complexity
- Confusing minimum spanning tree with shortest path (different problems)
- Not stopping once V-1 edges are added, wasting time scanning remaining edges
Best Answer (HR Friendly)
“Kruskal's algorithm builds the cheapest possible network connecting every node by always grabbing the next-cheapest connection that does not create a redundant loop. I use a union-find structure to instantly check whether two nodes are already connected, which is what keeps the cycle check fast even on large graphs.”
Code Example
class DisjointSet:
def __init__(self, vertices):
self.parent = {v: v for v in vertices}
self.rank = {v: 0 for v in vertices}
def find(self, v):
if self.parent[v] != v:
self.parent[v] = self.find(self.parent[v])
return self.parent[v]
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
return True
def kruskal(vertices, edges):
dsu = DisjointSet(vertices)
mst = []
for u, v, weight in sorted(edges, key=lambda e: e[2]):
if dsu.union(u, v):
mst.append((u, v, weight))
return mstFollow-up Questions
- How does path compression in union-find improve the amortized time complexity?
- How would you handle a disconnected graph when running Kruskal's algorithm?
- When would Prim's algorithm outperform Kruskal's algorithm?
- How would you find the maximum spanning tree using the same approach?
MCQ Practice
1. What is the dominant cost in Kruskal's algorithm's time complexity of O(E log E)?
Sorting E edges takes O(E log E), which dominates the near-constant amortized union-find operations.
2. What data structure does Kruskal's algorithm use to detect cycles efficiently?
Union-find lets the algorithm check in near O(1) amortized time whether two vertices are already connected.
3. How many edges does a minimum spanning tree contain for a connected graph with V vertices?
A spanning tree connecting V vertices always has exactly V - 1 edges, with no cycles.
Flash Cards
What greedy rule does Kruskal's algorithm follow? — Repeatedly add the cheapest edge that does not create a cycle.
What structure detects cycles in Kruskal's algorithm? — Union-find (disjoint-set), via find and union operations.
What is Kruskal's time complexity? — O(E log E), dominated by sorting the edges.
How many edges are in a minimum spanning tree of V vertices? — V - 1 edges.