Prim's Minimum Spanning Tree

Tree-expanding greedy MST algorithm leveraging key[] frontier weights and a priority queue to choose the minimum crossing edge each step.

Overview

Prim's algorithm grows a minimum spanning tree from an arbitrary start vertex by repeatedly taking the minimum-weight edge that connects the current tree to a new vertex (the cut frontier). It parallels Dijkstra's style but tracks edge weights instead of distances.

Core Steps

Pick arbitrary start vertex; set key[start]=0.
Push start into priority queue by key.
Extract-min vertex u not yet in tree.
For each edge (u,v), if v not in tree and w < key[v], update key[v], parent[v].
Repeat until all vertices added (n−1 edges chosen).

Why It Works

Cut Property: Each step chooses the lightest edge crossing the frontier cut.
Keys maintain current best crossing edge per outside vertex.
Extract-min yields a safe vertex addition.

Complexity

Binary Heap

O(m log n)

Fib Heap

O(m + n log n)

Dense Adj Matrix

O(n^2)

Choice of priority queue structure changes time bounds similarly to Dijkstra. For dense graphs, a simple array (O(n^2)) is competitive.

Comparison

Algorithm	Approach	Best For	Time
Prim (Heap)	Grow tree	Dense / general	O(m log n)
Prim (Matrix)	Scan keys	Very dense	O(n^2)
Kruskal	Merge forests	Sparse / sorted reuse	O(m log n)

Quick Facts

Inventor: Robert C. Prim (1957)
Also Known: Jarník–Prim–Dijkstra
Paradigm: Greedy cut expansion
Key Array: key[v] = best edge weight into tree
Supports: Negative weights

Next Steps

Study the priority queue updates and then watch the dynamic frontier evolve.

Theory Simulation All Graph Algorithms

Back: Kruskal Next:topological-sort