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.