Weighted Quick Union algorithm explained

I have been taking a course offered by coursera called Algorithms, and thought it would be a good idea to explain the Weighted quick union algorithm in more detail using Javascript.

So here’s the general definition: The weighted quick union algorithm allows us to keep information about items connected in a data structure. It works with a set of data containing n elements initially enumerated from 0 to n -1. The general idea behind it is to perform these basic operations:

• Union: It connects two nodes, initially every node’s root is the item itself, but every time nodes get connected to other nodes root changes depending on its weight, we will this more graphically later on.
• Connected: It validates whether two nodes are connected or not.

There are several applications for this algorithm, some of them are:

• Percolation (I’ll explain this one in a different article)
• Games (Go, Hex)
• Dynamic connectivity
• Morphological attribute openings and closings
• And… far way more!

Before jumping into code I would like to show you graphically what is going on, here’s the tree-alike diagram explained, let’s perform some union operations:

Initial Structure

Union (0, 2), here we have just joined the node 2 to node 0. However, you should bear in mind that node 0 now has 2 items in terms of the weighted algorithm node 0 has a weight of 2. Whereas the other nodes just have a weight of 1 by default.

Union (2, 4), for this case things get even more interesting since one of the main points of this algorithm as its name indicates, is weighting nodes every time it tries to union things. Now, we are joining node 4 and node 2, and as you can see node 2 is connected to node 0 that gives it more weight. Therefore, node 4 is joined to node 2’s root.

Let’s perform some more union operations…

Union(1, 3), Union(5, 6), Union(8, 7), so far so good, nothing really complex happening in here, just a bunch of simple unions

Union(6, 3), Union(8, 1) And here again for node 6 and 3 we weight our nodes, since their root weight 2 for both, we just choose one but pay close attention we didn’t join node 6 directly to 3 instead we joined their roots. The same happens with the union of node 8 and, we weight first and see that the tree of node 1 is bigger than the tree where node 8 is.

Union (2, 6), Union(1, 9) Finally, we join the remaining trees, and not necessarily but their roots instead we took nodes positions way down.

This is the beauty of this algorithm it is constantly weighting the node’s root to join them carefully and delicately. The picture above speaks by itself, the branches of this tree are short, we have just 3 levels of nodes. This would have not happened if we had not used the weight approach.

Ok enough talking let’s bring some code to better explain this awesome algorithm! You can find the full code in Codepen here.

For this example I’ve defined a finite structure of 10 items enumerated from 0 to 9, the algorithm will allow us to group these items in a tree-structured manner (you can think of a genealogical tree). That’s why every item on the array holds an object with two properties. weight: that indicates the number of items that specific node is connected to, by default is 1 since items are independent initially. root: you can see this one as the “father” of that node.

Graphically the structure looks like this:

Now that we have the structure to play around we can start connecting items by leveraging the union operation. For that I’ve declared the following method, please read comments to understand better what it is happening:

Using the code above, I’ve chosen to union the node 1 and 2, pay attention to the array both of them now share the same root. You can keep experimenting on the Codepen and see how the root changes every time you tie the nodes.

Finally, the Connected operation becomes easier, for two nodes given we just have to find out their root respectively and compare if both of them are the same. If so, it just means they are connected. Here’s the code:

And that is it, hope now you have a better understanding of this algorithm!