Definition

Prim is a minimum spanning tree algorithm that starts from one node and expands step by step, using a priority queue to pick the "cheapest edge that attaches to the tree".

Key Characteristics

• ✓Uses a priority queue: pops the cheapest edge that can attach to the tree first.
• ✓Greedy approach: at each step it grows the tree by one node at minimum cost.
• ✓Compares a single "edge that connects one node" — unlike Dijkstra's "sum of distance back to the source".
• ✓Often preferable to Kruskal on dense graphs (many edges).

Time Complexity