Kruskal's Algorithm (MST)

1. One-Liner

Kruskal sorts all edges by weight and adds the next lightest edge if it connects two different components (union-find detects cycles).

2. The Problem It Solves

Same as Prim: minimum spanning tree for a connected undirected weighted graph — often easier to implement with DSU on sparse graphs.

3. The Core Idea

Cut property / Kruskal: processing edges lightest-first, an edge is safe iff it does not close a cycle in the forest built so far.

4. How It Works (Step-by-Step)

Step	Action
1	Sort edges by weight ascending
2	Initialize DSU with V singleton sets
3	For each edge (u,v,w): if find(u)≠find(v), union and add w to total
4	Stop after V−1 edges added

5. Dry Run Example

Edges: (0,1,1), (1,2,2), (0,2,5). Take 0–1, then 1–2, skip 0–2 (cycle). Total 3.

6. Key Properties

Property	Value
Disjoint sets	Path compression + union by rank → α(V) amortized
Edge-centric	Natural for sparse E

7. Where It Is Used

Domain	Use
Same as Prim	Network design, image segmentation (graph cuts related)
Kaggle / ML	Clustering approximations

8. Interview Tips

Implement DSU cleanly; prove cycle avoidance equals cut optimality. Compare time vs Prim.

9. Comparison with Other Algorithms

	Kruskal	Prim
Sort	O(E log E)	No global sort
DSU	Yes	No
Sparse	Often wins	Dense graph alternative

10. Complexity


--	--
Time	O(E log E) for sort + O(E α(V)) for DSU
Space	O(V + E)

Implementation Example (PYTHON)

def kruskal(n, edges):
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb: return False
        parent[rb] = ra
        return True
    edges = sorted(edges, key=lambda e: e[2])
    total = 0
    for u, v, w in edges:
        if union(u, v):
            total += w
    return total