Overview
Prim's Algorithm grows one connected tree, using a priority queue to choose the lightest frontier edge.
CoreSource checked
Prim's Algorithm
Builds a minimum spanning tree by repeatedly attaching the cheapest edge from the tree to a new node.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Graph Traversal
- Difficulty
- Intermediate
- Family
- Greedy Graph Algorithm
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 5
- Code example
- Ready
- Visualization
- Ready
Core Concepts
priority queuefrontier edgesafe edgetree growth
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(E log V)
Average
O(E log V)
Worst
O(E log V)
Space
O(V + E)
When to Use
- Use when you have adjacency lists and want to grow one connected tree.
- Use when dense graph MSTs is a central requirement.
When Not to Use
- Avoid when the graph is disconnected and you need a spanning forest without special handling.
- Avoid when the graph changes faster than the traversal result can be reused.
What It Does
- Starts from one node
- Maintains frontier edge costs
- Adds the cheapest outside node
Use Cases
- Dense graph MSTs
- Adjacency-list graph processing
- Network expansion planning
Inputs
- Connected weighted undirected graph
- Start node
Outputs
- Minimum spanning tree edges
Key Formulas (1)
Frontier priority
priority(v) = minimum weight edge from tree to v
priority(v) = minimum weight edge from tree to vRanks outside nodes by their cheapest connection to the current tree.
Pseudocode
- 1.Choose a start node
- 2.Push its outgoing edges into a priority queue
- 3.Pop the cheapest edge that reaches an unvisited node
- 4.Add that node and its outgoing edges
- 5.Continue until every node is included
Canonical Example
- Input
- start = A, edges = A-B:1, B-C:2, A-C:4
- Output
- selected = [A-B, B-C]
- Explanation
- The tree first takes A-B, then reaches C more cheaply through B than directly from A.
Implementation Notes
- Ignore stale queue entries that point to nodes already included in the tree.
- Use explicit node ids and keep traversal state separate from graph storage.
- Keep a tiny example with expected output beside the implementation.
Common Pitfalls
- Using total path distance instead of single edge weight changes the algorithm into something else.
- Forgetting to track visited or finalized nodes can create repeated work or cycles.
- Not defining boundary, empty, or degenerate inputs before implementation.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow a connected tree expanding through its cheapest frontier edge.
Step 1 of 5: Choose a start node
graph-traversalNotes
The priority-queue structure resembles Dijkstra's Algorithm, but the priority is edge cost rather than path distance.
Sources (2)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Prim's Algorithm's standard algorithm design, invariants, and complexity analysis.
Open sourceThe Algorithm Design Manual
BookAlgorithm catalog support for Prim's Algorithm's problem context, known alternatives, and practical selection tradeoffs.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageSpecializesMinimum Spanning Tree
Prim's Algorithm solves the minimum spanning tree problem by growing a frontier.
UsesPriority Queue
Prim's Algorithm commonly uses a priority queue for candidate edges.
Related Algorithms
Tags
GraphWeighted GraphMinimum Spanning TreePriority QueueGreedy