Quick Union Java Implementation
I was studying the fast join algorithm. the example below was an example implementation. Can anyone explain to me what is going on inside the root method, you are welcome?
public class quickUnion {
private int[] id;
public void QuickUnionUF(int N){
id = new int [N];
for(int i = 0; i < N; i++){
id[i] = i;
}
}
private int root(int i){
while (i != id[i]){
i = id[i];
}
return i;
}
public boolean connected(int p, int q){
return root(p) == root(q);
}
public void union(int p, int q){
int i = root(p);
int j = root(q);
id[i] = j;
}
}
source to share
The basic principle of union search is that each element belongs to a disjoint set of elements. This means that if you draw a forest (a collection of trees), the forest will contain all the elements, and no element will be in two different trees.
When creating these trees, you can imagine that any node has a parent or is a root. In this implementation of union (and in most implementations of union search), the parent of each element is stored in an array in that index. Thus, the element equivalent to id [i] is the parent of i.
You may ask: What if I don't have a parent (aka root)? In this case, the agreement must be established by me for myself (i is its own parent). So id [i] == i just checks if we have reached the root of the tree.
Putting it all together, the root function traverses from the beginning of the node, all the way down to the tree (parent-parent) until it reaches the root. Then it returns the root.
As an aside: In order for this algorithm to get to the root faster, common implementations will "flatten" the tree: the fewer parents you need to traverse to get to the root, the faster the root function will return. Thus, in many implementations, you will see an extra step in which you set the parent of an element to its original grandfather (id [i] = id [id [i]]).
source to share
The main point of the algorithm is to always keep the root of one vertex equal to itself.
- Initialization: Initialization ID [i] = i. Each vertex is itself a root.
-
Merge root:
- If we concatenate root 5 and root 6. Suppose we want to concatenate root 6 into root 5. So id [6] = 5. id [5] = 5. → 5 is root.
- If we continue to concatenate 4 - 6. id [4] = 4 -> base root. id [6] = 5. → not the main root. We keep finding: id [5] = 5 -> base root. so we assign id [4] = 6
In all cases, we always keep the convention: if x is the base root, id[x] == x
this is the base point of the algorithm.
source to share
From the PDF file provided in the course Union find
The root i is id [id [id [... id [i] ...]]].
according to this example
public int root(int p){
while(p != id[p]){
p = id[p];
}
return p;
}
consider the situation:
Id [] elements will look like 
Now let's call
root(3)
Dry loop for loop inside root method:
source to share