Graph Algorithm
Kruskal's Algorithm
“The Forest Merger”
History
Published by Joseph Kruskal in 1956. While Prim's algorithm focuses on growing a single tree, Kruskal took a different approach: what if we just picked the best edges everywhere and worried about connecting them later?
It is an elegant example of how simple local rules can build a complex global structure.
How It Works
Kruskal's is edge-centric, not node-centric. It doesn't "grow" a tree; it merges disjoint sets (islands) until they become one continent.
The Algorithm Step-by-Step
- Sort: List every single edge in the graph, sorted from smallest weight to largest.
- Iterate: Walk through the sorted list.
- Check: Does this edge connect two nodes that are *already* connected (part of the same cluster)?
- Yes? Throw it away (it would create a cycle).
- No? Add it to the MST.
- Union: Merge the two clusters together.
- Repeat: Until you have edges.
The Secret Weapon: Union-Find The algorithm relies heavily on a data structure called "Union-Find" (or Disjoint Set). This structure allows us to check if two nodes are in the same group in near-constant time ().
The bottleneck is sorting the edges. The Union-Find operations are nearly instantaneous (inverse Ackermann function).
Storing the edge list and the Union-Find parent array.
The core data structure powering Kruskal's Algorithm.
How this algorithm appears during visualization.
Code Walkthrough
Real implementations in multiple programming languages. Select a language to view idiomatic code.
1class UnionFind:2 """Disjoint Set Union (DSU) with path compression and union by rank."""34 def __init__(self, n: int):5 self.parent = list(range(n))6 self.rank = [0] * n78 def find(self, x: int) -> int:9 """Find root with path compression."""10 if self.parent[x] != x:11 self.parent[x] = self.find(self.parent[x])12 return self.parent[x]1314 def union(self, x: int, y: int) -> bool:15 """Union by rank. Returns True if merged, False if already connected."""16 root_x, root_y = self.find(x), self.find(y)1718 if root_x == root_y:19 return False # Already in same set (would create cycle)2021 # Union by rank: attach smaller tree under larger tree22 if self.rank[root_x] < self.rank[root_y]:23 self.parent[root_x] = root_y24 elif self.rank[root_x] > self.rank[root_y]:25 self.parent[root_y] = root_x26 else:27 self.parent[root_y] = root_x28 self.rank[root_x] += 12930 return True313233def kruskal(n: int, edges: list[tuple[int, int, int]]) -> list[tuple[int, int, int]]:34 """Find Minimum Spanning Tree using Kruskal's algorithm.3536 Args:37 n: Number of vertices (0 to n-1)38 edges: List of (u, v, weight) tuples3940 Returns:41 List of edges in the MST as (u, v, weight) tuples42 """43 # Sort edges by weight (greedy approach)44 sorted_edges = sorted(edges, key=lambda e: e[2])4546 uf = UnionFind(n)47 mst: list[tuple[int, int, int]] = []4849 for u, v, weight in sorted_edges:50 # If u and v are in different components, add edge51 if uf.union(u, v):52 mst.append((u, v, weight))5354 # MST complete when we have n-1 edges55 if len(mst) == n - 1:56 break5758 return mstReal World Use Cases
- 1Landing Cables (connecting cities efficiently)
- 2Image Segmentation (grouping pixels)
- 3Approximating the Traveling Salesperson Problem
- 4Network reliability analysis
Key Insights
- It builds a 'Forest' of trees that eventually merge.
- It is excellent for Sparse Graphs (fewer edges).
- It handles disconnected graphs naturally (produces a Spanning Forest).
- It relies entirely on the sorting step.
When to Use
Use Kruskal's on sparse graphs, or when you already have a list of edges sorted by weight. It is also easier to implement if you have a Union-Find class ready.
When NOT to Use
Avoid on dense graphs. Sorting edges takes longer than Prim's approach when is large ().
Interview Tip
The interview question is almost never 'Implement Kruskal.' It is 'Implement Union-Find.' Make sure you understand Path Compression and Union by Rank.