Finds minimum spanning tree by sorting edges and using Union-Find
Time: O(E log E)
Space: O(V)
Use Case: Network design, clustering, circuit design
Algorithm Execution
Select an algorithm and generate steps to begin visualization
About Kruskal's MST Algorithm
Kruskal's algorithm finds a minimum spanning tree by considering edges in increasing order of weight and adding each edge that does not create a cycle. Unlike Prim's tree-growing approach, Kruskal grows a forest of components that gradually merge into one tree.
How it works
After sorting all edges by weight, the algorithm walks through them smallest first. For each edge it uses a Union-Find (disjoint set) structure to check in near-constant time whether the two endpoints are already in the same component. If they are not, the edge is accepted and the components are merged; otherwise it is skipped as a cycle edge. Sorting dominates the cost, giving O(E log E) time.
Applications
Kruskal's algorithm is preferred for sparse graphs and for problems where edges arrive pre-sorted, such as single-linkage clustering, image segmentation, and network design with cost tiers. The embedded Union-Find structure is itself a top interview topic, covering path compression and union by rank.