Prim's Algorithm
HardGrow the tree by its cheapest outgoing edge
Problem
Build a minimum spanning tree by growing it one cheapest edge at a time.
Grow the tree from any node, always adding the cheapest edge that reaches a new node (min-heap).
The idea
Prim grows one connected tree outward from any start node. Each step it looks at all edges crossing from the tree to the outside and greedily takes the cheapest, pulling in a new node. This is safe by the cut property, and after V-1 additions every node is connected with the least possible total weight. A min-heap makes 'cheapest crossing edge' fast.
The trick
- The cut property: the cheapest edge leaving the current tree is always safe to add to some MST.
- Prim keeps one growing tree; Kruskal instead merges separate forests — both reach a minimum spanning tree.
Step 1 of 10. A Minimum Spanning Tree connects every node with the least total edge weight. Start the tree with just A. tree A, weight 0.
1tree = {start}; total = 02min-heap of edges leaving the tree3repeat until tree has all nodes:4 pick the cheapest edge to a NEW node; add that node; total += weight5return total // minimum spanning tree weightInput
- nodes
- 5, 7 edges
Memory
- tree
- A
- add edge
- —
Output
- weight
- 0
- MST weight
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- n=5, edges=[[0,1,2],[0,3,6],[1,2,3],[1,3,8],[1,4,5],[2,4,7],[3,4,9]]
- Output:
- 16
- Explanation:
- Cheapest tree connecting all nodes weighs 16.
Example 2
- Input:
- n=2, edges=[[0,1,5]]
- Output:
- 5
- Explanation:
- One edge → weight 5.
Example 3
- Input:
- n=3, edges=[[0,1,1],[1,2,1],[0,2,3]]
- Output:
- 2
- Explanation:
- Pick the two 1-edges → 2.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.