Skip to interview prep
Apexed

30. How do Prim's and Kruskal's algorithms build a minimum spanning tree?

MediumGraph algorithms

Technical
Show model answer

Kruskal sorts edges by weight and adds each edge that does not create a cycle, checked with union-find: O(E log E). Prim grows one tree from a start vertex, repeatedly adding the cheapest edge leaving the tree, using a priority queue: O(E log V). Both rely on the cut property: the lightest edge across any cut belongs to some MST.

How do Prim's and Kruskal's algorithms build a minimum spanning tree — Data structures & algorithms interview question — Apexed