[Verse 1]
Graph's got edges with weights to measure
Finding minimum tree's my pleasure
Start with vertices standing alone
Build connections, make them one zone
Sort all edges by their cost ascending
Cheapest first, that's never ending
Union-find keeps track of sets
Avoiding cycles, no regrets
[Chorus]
Sort the edges, pick the least
Union-find will guide the beast
Check for cycles, skip if found
Minimum spanning tree is crowned
Kruskal's way, the greedy choice
Let the algorithm be your voice
Edge by edge, we build it right
Spanning tree shines bright tonight
[Verse 2]
Disjoint sets with parent pointers
Path compression, efficiency joiners
Find the root of every node
Union by rank breaks the code
If two vertices share same parent
Skip that edge, it's not apparent
Different sets mean safe to merge
One more edge on spanning verge
[Chorus]
Sort the edges, pick the least
Union-find will guide the beast
Check for cycles, skip if found
Minimum spanning tree is crowned
Kruskal's way, the greedy choice
Let the algorithm be your voice
Edge by edge, we build it right
Spanning tree shines bright tonight
[Bridge]
Time complexity's E log E for the sort
Union-find's nearly constant support
Greedy algorithm proves optimal
Mathematical truth, not just topical
MST connects all vertices clean
Minimum weight, efficient machine
[Verse 3]
Initialize each vertex alone
Make set operation, each one's own
Process edges in sorted order
Union-find maintains the border
Continue till we've got V minus one
Edges chosen, algorithm's done
Connected graph with minimum cost
Kruskal's magic, no weight is lost
[Chorus]
Sort the edges, pick the least
Union-find will guide the beast
Check for cycles, skip if found
Minimum spanning tree is crowned
Kruskal's way, the greedy choice
Let the algorithm be your voice
Edge by edge, we build it right
Spanning tree shines bright tonight
[Outro]
From network design to clustering data
MST's the solution, no need to debate ya
Kruskal showed us the optimal way
Greedy choices win the day