[Verse 1]
Start with a graph, edges all scattered around
Weighted connections, some heavy, some light to be found
Kruskal's the name of the game we're about to play
Find the minimum spanning tree, that's the only way
Sort all the edges from smallest to largest weight
Union-Find structure keeps track of our connected state
Check every edge, make sure no cycles form
Connect the components, that's the algorithm's norm
[Chorus]
Sort the edges, check for cycles, union if it's clear
Minimum spanning tree, Kruskal makes it appear
Disjoint sets and weighted paths, greedy choice each time
Connect them all with minimum cost, algorithm so fine
Sort, check, union, repeat until the tree's complete
Kruskal's algorithm, makes the solution sweet
[Verse 2]
Initialize each vertex as its own separate set
Union-Find will tell us if components have met
Take the lightest edge that hasn't been processed yet
If endpoints are in different sets, then it's a safe bet
Add it to our spanning tree, union those two sets
Keep the forest growing, but no cycles we'll beget
Edges equal to vertices minus one we need
Kruskal's greedy strategy will surely succeed
[Chorus]
Sort the edges, check for cycles, union if it's clear
Minimum spanning tree, Kruskal makes it appear
Disjoint sets and weighted paths, greedy choice each time
Connect them all with minimum cost, algorithm so fine
Sort, check, union, repeat until the tree's complete
Kruskal's algorithm, makes the solution sweet
[Bridge]
Time complexity O of E log E for the sort
Union-Find operations keep the runtime short
Path compression and union by rank optimize
Find and union operations in nearly constant time
Greedy algorithm that always makes the right choice
Minimum spanning tree gives networks a strong voice
[Verse 3]
Applications everywhere from networks to design
Connecting cities with cables, keeping costs in line
Circuit boards and water pipes, roads between the towns
Kruskal finds the cheapest way to link without breaking down
Start with sorted edges, use Union-Find to track
Which components are connected, there's no looking back
When all vertices connected in one spanning tree
Kruskal's work is finished, minimum cost guarantee
[Chorus]
Sort the edges, check for cycles, union if it's clear
Minimum spanning tree, Kruskal makes it appear
Disjoint sets and weighted paths, greedy choice each time
Connect them all with minimum cost, algorithm so fine
Sort, check, union, repeat until the tree's complete
Kruskal's algorithm, makes the solution sweet
[Outro]
Remember Kruskal's method when you need to span
Sort then union-find, that's the master plan
Minimum cost connections, no cycles in sight
Spanning tree algorithm, get it right every time