← Back to DSA Animator
Min Cost to Connect All Points LC #1584 Medium Graph · Prim's MST
Problem

Connect all points with minimum total cost. Cost = Manhattan distance. Prim's MST: pick min-dist non-MST point, add to MST, update minDist.

Example
Input: [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Try Examples
Custom: points as x,y (space separated)
Approach
Prim's MST
minDist[i]=min distance from pt i to MST. Pick min non-MST, add to MST, update minDist. Sum = total cost.
Points & MST Edges
Load an example.
Variables
Pick u
—
minDist[u]
—
cost
—
MST size
—
Step Logic
Press ▶ Play or Next Step.
✓
Ready
0/0
Select example and Play.
Algorithm
1
minDist[0]=0, others=∞
2
Pick min non-MST, add to MST
3
Update minDist for rest
Time
O(n²)
Space
O(n)
Why Prim's

Complete graph (all pairs). minDist[v]=cheapest edge from v to current MST. Greedy pick gives MST.