Learn
Prim's Algorithm
Prim's Algorithm builds the Minimum Spanning Tree (MST) by growing from a starting vertex. You repeatedly add the minimum weight edge connecting the tree to an unvisited vertex.
Unlike Kruskal, Prim's works better on dense graphs because you don't need to sort all edges upfront.
function prim(graph, n):
visited = array of size n, initialized to false
pq = min-priority queue
pq.push((0, 0))
mstWeight = 0
edgesUsed = 0
while pq is not empty and edgesUsed < n:
(weight, u) = pq.pop()
if visited[u]:
continue
visited[u] = true
mstWeight = mstWeight + weight
edgesUsed = edgesUsed + 1
for each edge (u, v, w) from u:
if not visited[v]:
pq.push((w, v))
if edgesUsed != n:
return -1
return mstWeight
Prim vs Kruskal: Prim works better on dense graphs. Kruskal works better on sparse graphs where sorting fewer edges is faster.
Skip optimization: When you pop a vertex from the queue, skip it if already visited.
Applications: You use Prim for network cable layout, circuit design, maze generation, and hierarchical clustering.
Time complexity: with a binary heap.