Spellbook · projects
Wizard Card · about
Arithmancy · bend the gridOwl Post · nowRecords · resume
Avyaya's Machine

Spellbook · projects

×
p. 15

experiment no. 008 · screensaver

Prim, on repeat.

my neetcode solution to min cost to connect all points, replayed step by step as a screensaver. it picks new points, builds the tree, holds for a second, then starts all over again

algorithmsgraphsNeetCodecanvas

annotation

i left the stale pops in on purpose. the C++ does them, so the replay should too

Prim's algorithm building a minimum spanning treefull screen
Prim's algorithm building a minimum spanning tree. Opens full screen in a new tab from the link above.

What you are looking at

twenty random points on a 30 × 30 grid. the goal is connecting all of them as cheaply as possible, where each edge costs the Manhattan distance between its two ends: |x₁ − x₂| + |y₁ − y₂|.

Prim's algorithm grows the tree starting from one point. every time a point joins, every edge from it to something outside the tree gets thrown onto a min-heap, those are the faint candidate lines you see. the cheapest one gets popped off, and if that point's already in the tree it's just a stale entry that gets tossed, otherwise that edge joins the tree. the status line at the bottom is narrating every push and pop straight from the C++.

this is a faithful trace of minCostConnectPoints, stale pops and all, not some cleaned-up version of the algorithm.