[Verse 1]
Started with a graph, connections everywhere
Weighted edges linking nodes, but we don't really care
About the mess, we need the best, minimum spanning tree
Prim's algorithm got the key, let me tell you how it's free
Pick a starting vertex, any one will do
Initialize the empty set, that's our tree so true
Mark that vertex visited, now we're in the game
Every step we take from here follows the same refrain
[Chorus]
Find the minimum, cross the border line
From visited to unvisited, that edge is mine
Add the vertex, mark it done, keep the tree alive
Prim's algorithm, step by step, watch the solution thrive
Minimum edge, cross the cut, add the node
Repeat until we've built the minimum spanning code
[Verse 2]
Priority queue keeps it clean, edges sorted by their weight
Smallest first, that's the rule, never hesitate
From the visited set we scan, look across the divide
Find the cheapest bridge to cross to the other side
Update the queue with every step, new edges to explore
But only those that cross the cut, connecting to our core
Greedy choice at every turn, locally optimal
But here's the beauty of this algorithm, it's globally optimal
[Chorus]
Find the minimum, cross the border line
From visited to unvisited, that edge is mine
Add the vertex, mark it done, keep the tree alive
Prim's algorithm, step by step, watch the solution thrive
Minimum edge, cross the cut, add the node
Repeat until we've built the minimum spanning code
[Bridge]
Cut property guarantees the choice we make is right
Safest edge across the cut will optimize our sight
No cycles forming in our tree, that's the spanning way
Connected graph with n minus one edges at the end of day
Time complexity looking clean, E log V with heap
Adjacency list representation keeps the runtime cheap
[Verse 3]
Jarnik found it first in nineteen-thirty, that's a fact
Prim rediscovered later, got his name attached
Dijkstra did the same in fifty-nine, independent mind
Three brilliant minds, same solution, beautifully designed
Applications everywhere, network design so tight
Minimum cost to connect all nodes, electrical insight
Circuit boards and water pipes, roads between the towns
Prim's algorithm finds the path with the lowest cost around
[Chorus]
Find the minimum, cross the border line
From visited to unvisited, that edge is mine
Add the vertex, mark it done, keep the tree alive
Prim's algorithm, step by step, watch the solution thrive
Minimum edge, cross the cut, add the node
Repeat until we've built the minimum spanning code
[Outro]
From one vertex to the rest, growing tree with every beat
Minimum spanning guaranteed when the algorithm's complete