[Verse 1]
Starting with a graph, connections everywhere
Vertices scattered, edges floating in the air
Pick any node to plant your rooted tree
Mark it visited, set the others free
Initialize a queue with zero-weight priority
Every neighbor gets their edge cost measured carefully
[Chorus]
Prim builds trees, greedy choice guaranteed
Minimum span, grab the cheapest strand
Cut that crosses, forest to connected land
Prim builds trees, greedy choice guaranteed
Lightest edge from visited to unexplored terrain
[Verse 2]
Heap extraction pulls the smallest weight on top
Adjacent vertex joins the growing crop
Update priorities for every neighboring friend
If cheaper paths exist, the old costs bend
Relaxation keeps the spanning forest lean
While visited markers paint the nodes we've seen
[Chorus]
Prim builds trees, greedy choice guaranteed
Minimum span, grab the cheapest strand
Cut that crosses, forest to connected land
Prim builds trees, greedy choice guaranteed
Lightest edge from visited to unexplored terrain
[Bridge]
Logarithmic extraction from the binary heap
V minus one iterations, promises we keep
Cut property proves our greedy method sound
Optimal substructure in every edge we've found
[Verse 3]
Dense graphs favor Prim over Kruskal's way
Adjacency lists make the neighbor lookup play
Each iteration grows exactly one vertex more
Until the spanning tree connects from shore to shore
Time complexity V squared with simple arrays
E log V when heaps optimize our days
[Chorus]
Prim builds trees, greedy choice guaranteed
Minimum span, grab the cheapest strand
Cut that crosses, forest to connected land
Prim builds trees, greedy choice guaranteed
Lightest edge from visited to unexplored terrain
[Outro]
Connected components unified at last
Minimum spanning tree, the die is cast