Kruskal’s Algorithm & Quick Union

In 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.

The gist:

  1. For each edge by weight ascending
  2. If nodes are in same component, forget/skip
  3. 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:

Leave a Reply

Your email address will not be published. Required fields are marked *