Prim's algorithm

An algorithm that builds a minimum spanning tree by growing it from one start vertex, always adding the cheapest edge leading out of the tree.

In more detail

A min-heap holds the frontier edges; each step pops the cheapest one and skips it if it leads back into the tree. Like Dijkstra's algorithm it costs O(E log E) with a binary heap. The cut property guarantees each chosen edge belongs to an MST.

Related terms

Taught in

References