Kruskal's Algorithm: Implementation and Analysis
You'll learn how to implement Kruskal's algorithm efficiently and understand why its runtime is O(E log E).
Now that you've learned the conceptual overview and the union-find data structure, let's put them together into working code and analyze the performance.
Implementation Steps
Kruskal's algorithm sorts all edges by weight, then greedily adds edges that don't create cycles:
def kruskal_mst(n, edges):
# edges is a list of (weight, u, v) tuples
# Step 1: Sort edges by weight - O(E log E)
edges.sort()
# Step 2: Initialize union-find - O(V)
parent = list(range(n))
rank = [0] * n
def find(x):
if parent[x] != x:
parent[x] = find(parent[x]) # path compression
return parent[x]
def union(x, y):
root_x, root_y = find(x), find(y)
if root_x == root_y:
return False
# Union by rank
if rank[root_x] < rank[root_y]:
parent[root_x] = root_y
elif rank[root_x] > rank[root_y]:
parent[root_y] = root_x
else:
parent[root_y] = root_x
rank[root_x] += 1
return True
# Step 3: Process edges - O(E * α(V))
mst = []
for weight, u, v in edges:
if union(u, v): # No cycle created
mst.append((weight, u, v))
return mst
Time Complexity Analysis
- Sorting edges: O(E log E) dominates
- Union-find operations: E operations × α(V) ≈ O(E) where α is the inverse Ackermann function (practically constant)
- Total: O(E log E) or equivalently O(E log V), since E ≤ V²
The union-find optimizations (path compression + union by rank) make cycle detection nearly free compared to sorting!
Key Takeaway: Kruskal's algorithm runs in O(E log E) time, dominated by sorting edges, with union-find providing near-constant-time cycle detection through path compression and union by rank optimizations.