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
- minimum spanning tree — The spanning tree of a weighted, connected graph whose edges have the smallest possible total weight.
- Kruskal's algorithm — An algorithm that builds a minimum spanning tree by sorting all edges by weight and adding each one unless it would create a cycle.
- min-heap — A heap in which every parent is less than or equal to its children, so the minimum is at the root; a max-heap reverses the order.
- cut property — The fact that, for any way of splitting a graph's vertices into two groups, the cheapest edge crossing between the groups belongs to some minimum spanning tree.
- frontier — The set of discovered but not yet processed vertices at the edge of a search, waiting in its queue, stack or heap.
Taught in
- Minimum Spanning Trees: Kruskal And Prim — Algorithms & Data Structures for Working Engineers