Prim's MST Algorithm

Prim's algorithm builds a minimum spanning tree (MST) of a weighted undirected graph, the subset of edges that connects every vertex with the smallest possible total weight. It grows a single tree outward from an arbitrary start vertex, always attaching the cheapest edge that reaches a new vertex.

How it works

The algorithm keeps a priority queue of edges that cross from the tree to the rest of the graph. At each step it extracts the minimum-weight crossing edge, adds its new endpoint to the tree, and inserts that vertex's edges into the queue. The cut property of MSTs guarantees each chosen edge belongs to some minimum spanning tree. With a binary heap the running time is O(E log V).

Applications

Prim's algorithm designs low-cost networks: electrical grids, fiber and telecom layouts, water pipelines, and chip wiring. It also supports clustering and image segmentation. Interviews often pair it with Kruskal's algorithm to test understanding of greedy correctness arguments.