Kruskal's MST Algorithm

Greedy Minimum Spanning Tree via Disjoint Set Union.

Strategy

Greedy Forest

Sort edges and merge components

Data Structure

DSU

Disjoint Set Union for cycles

Optimal

Minimum Weight

Guarantees MST for connected graph

When to Use Kruskal's

Finding MST in a sparse graph (fewer edges)
When edges are already sorted or sorting is cheap
Constructing minimum cost spanning forest
Parallel implementation is not required (Prim is often better for that)

Core Idea

Kruskal's treats every node as an individual tree. It sorts all edges by weight and tries to add them one by one. An edge is added if and only if it connects two different trees (components), merging them into one. This process repeats until only one tree remains.

Algorithm Metrics

Time

O(E log E) or O(E log V)

Space

O(V + E)

Approach

Edge-based

Best for

Sparse graphs

Back: Floyd-Warshall Next: Prim's MST