Problem context and objectives
Mission briefing
Realm network architect · Routes have costs, dependencies, and unreliable bridges
Choose the next frontier that preserves the route guarantee: The Point Constellation.
One locally tempting edge can invalidate the whole journey.
How you win
- 1Recognize when Prim minimum spanning tree matches the clues
- 2Keep this true after every move: the visited points form one tree extendable to a minimum spanning tree
- 3Reach the result within O(n squared) with dense frontier updates
Rules and pressure
- Target cost: O(n squared) with dense frontier updates
- State rule: the visited points form one tree extendable to a minimum spanning tree
Lesson 1 of 3
Live algorithm trace
Prim minimum spanning tree
Complete execution1 of 6
0,0
seed
2,2
3,10
5,2
7,0
Seed point 0 with zero connection cost.
1
best[0] = 02
repeat n times3
choose unvisited point with smallest best cost4
add its cost to total5
update every unvisited Manhattan edge6
return totalbest = [0,inf,inf,inf,inf]total = 0
Truth to preserve / Cost target
Truth to preserve
the visited points form one tree extendable to a minimum spanning tree
Cost target
O(n squared) with dense frontier updates
Prim grows a connected tree by repeatedly taking the cheapest edge from the tree to an unvisited point. Manhattan distance supplies every implicit complete-graph edge weight.
Your call · What should guide every step of this algorithm?