n my previous post
I implemented Prim’s algorithm with pairing heap. Now, here’s another way to find the minimum spanning tree, using Kruskal’s algorithm (Wikipedia
) with quick union. If you compare the code between posts, this is a whole lot simpler.
- For each edge by weight ascending
- If nodes are in same component, forget/skip
- Else take edge and merge the two components
Here’s my implementation used in the solving of SPOJ 368. Cobbled Streets CSTREET, in git and below: