Kruskal Algorithm

overview

Summary

Kruskal is a greedy algorithm for building a minimum spanning tree of a weighted, undirected graph. It sorts edges by weight and adds the next lightest edge that does not form a cycle, using a union-find data structure to check connectivity fast. Its time complexity is O(E log E) due to sorting, and it works well on sparse graphs. Common uses include network design, road layout, and single-linkage clustering.