Kruskal's Algorithm is another way to find a Minimum Spanning Tree (MST) in a graph. It works by iteratively adding the cheapest available edge that connects two previously disconnected components, without forming a cycle. It is efficient for sparse graphs and uses a Union-Find data structure to detect cycles. Compare it with Prim’s Algorithm, which grows the MST from a single vertex, or Borůvka’s Algorithm which merges components in parallel.
sort edges by weight (ascending)
MST = empty set
for each vertex v:
create a disjoint set {v}for each edge (u, v):
if find(u) ≠ find(v):
add (u, v) to MST
union(u, v)
Kruskal's algorithm sorts all edges by weight and greedily considers them. DSU efficiently checks whether the endpoints of a candidate edge belong to the same connected component (find) to avoid forming cycles, and merges components (union).
Kruskal's is faster for sparse graphs (E ≈ V) because edge sorting is quick. Prim's (especially with adjacency lists or Fibonacci heaps) performs better on dense graphs (E ≈ V²) where handling all V² edges in DSU is slower.
Union by Rank attaches the shallower tree under the deeper tree to keep tree height bounded by O(log V). Path Compression flattens the tree during find operations by pointing visited nodes directly to the root. Together, they reduce the amortized cost per DSU operation, making Kruskal's overall runtime dominated by edge sorting O(E log E).
to join the discussion
Hand-picked resources to deepen your understanding
© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0