Learn
Kruskal's Algorithm
Kruskal's Algorithm finds the Minimum Spanning Tree (MST) by greedily adding the smallest edge that doesn't create a cycle. It uses Union-Find to efficiently check connectivity.
An MST connects all vertices with minimum total edge weight using exactly edges.
text
function kruskal(edges, n):
sort edges by weight in ascending order
parent = array where parent[i] = i
rank = array of size n, initialized to 0
mstWeight = 0
edgesUsed = 0
for each edge (u, v, weight) in sorted edges:
rootU = find(parent, u)
rootV = find(parent, v)
if rootU != rootV:
union(parent, rank, rootU, rootV)
mstWeight = mstWeight + weight
edgesUsed = edgesUsed + 1
if edgesUsed != n - 1:
return -1
return mstWeight
Union-Find operations:
text
function find(parent, x):
if parent[x] != x:
parent[x] = find(parent, parent[x])
return parent[x]
function union(parent, rank, x, y):
if rank[x] < rank[y]:
parent[x] = y
else if rank[x] > rank[y]:
parent[y] = x
else:
parent[y] = x
rank[x] = rank[x] + 1
Applications: You use Kruskal for network design, clustering, image segmentation, and approximating traveling salesman.
Time complexity: for sorting. Union-Find runs in nearly per operation.
Space complexity: for the Union-Find structure.