[Verse 1]
Graph stretched out like a city map, edges weighted with the cost to travel
Kruskal's vision: minimal spanning tree, watch the cheapest connections unravel
Sort those edges by their price tags, ascending order like a shopping list
Union-find keeps cycles distant, disjoint sets with iron fists
[Chorus]
Sort and sweep, pick the cheap, cycles sleep when sets don't meet
Kruskal builds with greedy speed, minimum tree guaranteed
Union-find keeps forests clean, spanning tree's the final scene
Sort and sweep, pick the cheap, algorithm's complete
[Verse 2]
Disjoint set forest in my memory, parent pointers climbing tall
Path compression flattens hierarchies, union by rank prevents the fall
Find the root with path collapse, make set checks blazingly fast
Alpha inverse time complexity, near-constant speed that's built to last
[Chorus]
Sort and sweep, pick the cheap, cycles sleep when sets don't meet
Kruskal builds with greedy speed, minimum tree guaranteed
Union-find keeps forests clean, spanning tree's the final scene
Sort and sweep, pick the cheap, algorithm's complete
[Bridge]
Edge by edge, we test connection
Different components get selection
Same root means rejection
Cycle detection, forest protection
[Verse 3]
Greedy choice at every junction, local optimum builds global best
Spanning tree with minimum weight sum, Kruskal's proof puts doubt to rest
E log E for sorting edges, alpha E for union operations
Network cables, circuit traces, real-world graph optimizations
[Chorus]
Sort and sweep, pick the cheap, cycles sleep when sets don't meet
Kruskal builds with greedy speed, minimum tree guaranteed
Union-find keeps forests clean, spanning tree's the final scene
Sort and sweep, pick the cheap, algorithm's complete
[Outro]
From disconnected to connected
Minimum cost, maximum respect
Kruskal's legacy perfected
Spanning trees architectected