DSA — Kruskal's Algorithm

What is Kruskal's Algorithm?

Finds the minimum spanning tree by adding edges in order of weight.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

def kruskal(edges, n):
    edges.sort(key=lambda x: x[2])
    uf = UnionFind(n)
    mst = []
    
    for u, v, weight in edges:
        if uf.union(u, v):
            mst.append((u, v, weight))
            if len(mst) == n - 1:
                break
    
    return mst

Time Complexity

Operation	Complexity
Sort edges	O(E log E)
Union-Find operations	O(E α(V))

Applications

• Network design
• Clustering
• Approximation algorithms

Mini Practice

1. Implement Kruskal's algorithm
2. Use Union-Find data structure
3. Find minimum spanning tree
4. Compare with Prim's algorithm

Up Next

Continue with Prim's Algorithm — another MST algorithm.