Quick Union Java Implementation

Question

I've been studying the quick union algorithm. the code below was the example for the implementation. Can someone explain to me what happens inside the root method please?

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;
    }
}

Answer 1

The core principle of union find is that each element belongs to a disjoint set of elements. This means that, if you draw a forest (set of trees), the forest will contain all the elements, and no element will be in two different trees.

When building these trees, you can imagine that any node either has a parent or is the root. In this implementation of union find (and in most union find implementations), the parent of each element is stored in an array at that element's index. Thus the element equivalent to id[i] is the parent of i.

You might ask: what if i has no parent (aka is a root)? In this case, the convention is to set i to itself (i is its own parent). Thus, id[i] == i simply checks if we have reached the root of the tree.

Putting this all together, the root function traverses, from the start node, all the way up the tree (parent by parent) until it reaches the root. Then it returns the root.

As an aside: In order for this algorithm to get to the root more quickly, general implementations will 'flatten' the tree: the fewer parents you need to get through to get to the root, the faster the root function will return. Thus, in many implementations, you will see an additional step where you set the parent of an element to its original grandparent (id[i] = id[id[i]]).

Answer 2

The main point of algorithm here is: always keep root of one vertex equals to itself.

1. Initialization: Init id[i] = i. Each vertex itself is a root.

2. Merge Root:

   • If we merge root 5 and root 6. Assume that we want to merge root 6 into root 5. So id[6] = 5. id[5] = 5. --> 5 is root.
   • If we continue to merge 4 to 6. id[4] = 4 -> base root. id[6] = 5. -> not base root. We continue to find: id[5] = 5 -> base root. so we assign id[4] = 6

In all cases, we always keep convention: if x is base root, id[x] == x That is the main point of algorithm.

Answer 3

From Pdf file provided in the course Union find

Root of i is id[id[id[...id[i]...]]].

according to the given example

  public int root(int p){

  while(p != id[p]){

      p = id[p];    
  }
  return p;
  }

lets consider a situation :

The elements of id[] would look like

Now lets call

    root(3)

The dry run of loop inside root method is:

Answer 4

To understand the role of the root method, one needs to understand how this data structure is helping to organise values into disjoint sets.

It does so by building trees. Whenever two independent values and are said to belong to the same set, is made a child of (which then is the parent of ). If however already has a parent, then we first move to that parent of , and the parent of that parent, ...until we find an ancestor which has no parent. This is root(p), lets call it '. We do the same with if it has a parent. Let's call that ancestor '. Finally, ' is made a child '. By doing that, we implicitly make the original and members of the same tree.

How can we know that and are members of the same tree? By looking up their roots. If they happen to have the same root, then they are necessarily in the same tree, i.e. they belong to the same set.

Example

Let's look at an example run:

QuickUnionUF array = new QuickUnionUF(10);

This will create the following array:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

This array represents edges. The from-side of an edge is the index in the array (0..9), and the to-side of the same edge is the value found at that index (also 0..9). As you can see the array is initialised in a way that all edges are self-references (loops). You could say that every value is the root of its own tree (which has no other values).

Calling root on any of the values 0..9, will return the same number, as for all i we have id[i] == i. So at this stage root does not give us much.

Now, let's indicate that two values actually belong to the same set:

array.union(2, 9); 

This will result in the assignment id[2] = 9 and so we get this array:

[0, 1, 9, 3, 4, 5, 6, 7, 8, 9]

Graphically, this established link be represented as:

       9
      /
     2

If now we call root(2) we will get 9 as return value. This tells us that 2 is in the same set (i.e. tree) as 9, and 9 happens to get the role of root of that tree (that was an arbitrary choice; it could also have been 2).

Let's also link 3 and 4 together. This is a very similar case as above:

array.union(3, 4);

This assigns id[3] = 4 and results in this array and tree representation:

[0, 1, 9, 4, 4, 5, 6, 7, 8, 9]

       9         4
      /         / 
     2         3

Now let's make it more interesting. Let's indicate that 4 and 9 belong to the same set:

array.union(4, 9);

Still root(4) and root(9) just return those same numbers (4 and 9). Nothing special yet... The assignment is id[4] = 9. This results in this array and graph:

[0, 1, 9, 4, 9, 5, 6, 7, 8, 9]

       9
      / \ 
     2   4
        /
       3

Note how this single assignment has joined two distinct trees into one tree. If now we want to check whether 2 and 3 are in the same tree, we call

if (connected(2, 3)) /* do something */

Although we never said 2 and 3 belonged to the same set explicitly, it should be implied from the previous actions. connected will now use calls to root to imply that fact. root(2) will return 9, and also root(3) will return 9. We get to see what root is doing... it is walking upwards in the graph towards the root node of the tree it is in. The array has all the information needed to make that walk. Given an index we can read in the array which is the parent (index) of that number. This may have to be repeated to get to the grandparent, ...etc: It can be a short or long walk, depending how many "edges" there are between the given node and the root of the tree it is in.

Answer 5

/**
 * Quick Find Java Implementation Eager's Approach
 */
package com.weekone.union.quickfind;

import java.util.Random;

/**
 * @author Ishwar Singh
 *
 */
public class UnionQuickFind {

    private int[] itemsArr;

    public UnionQuickFind() {
        System.out.println("Calling: " + UnionQuickFind.class);
    }

    public UnionQuickFind(int n) {
        itemsArr = new int[n];
    }

    // p and q are indexes
    public void unionOperation(int p, int q) {

        // displayArray(itemsArr);
        int tempValue = itemsArr[p];
        if (!isConnected(p, q)) {
            itemsArr[p] = itemsArr[q];
            for (int i = 0; i < itemsArr.length; i++) {
                if (itemsArr[i] == tempValue) {
                    itemsArr[i] = itemsArr[q];
                }
            }
            displayArray(p, q);
        } else {
            displayArray(p, q, "Already Connected");
        }

    }

    public boolean isConnected(int p, int q) {
        return (itemsArr[p] == itemsArr[q]);
    }

    public void connected(int p, int q) {

        if (isConnected(p, q)) {
            displayArray(p, q, "Already Connected");
        } else {
            displayArray(p, q, "Not Connected");
        }
    }

    private void displayArray(int p, int q) {
        // TODO Auto-generated method stub
        System.out.println();
        System.out.print("{" + p + " " + q + "} -> ");
        for (int i : itemsArr) {
            System.out.print(i + ", ");
        }
    }

    private void displayArray(int p, int q, String message) {
        System.out.println();
        System.out.print("{" + p + " " + q + "} -> " + message);

    }

    public void initializeArray() {
        Random random = new Random();
        for (int i = 0; i < itemsArr.length; i++) {
            itemsArr[i] = random.nextInt(9);
        }
    }

    public void initializeArray(int[] receivedArr) {
        itemsArr = receivedArr;
    }

    public void displayArray() {
        System.out.println("INDEXES");
        System.out.print("{p q} -> ");
        for (int i : itemsArr) {
            System.out.print(i + ", ");
        }
        System.out.println();
    }

}


Main Class:- 

/**
 * 
 */
package com.weekone.union.quickfind;

/**
 * @author Ishwar Singh
 *
 */
public class UQFClient {

    /**
     * @param args
     */
    public static void main(String[] args) {

        int[] arr = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        int n = 10;
        UnionQuickFind unionQuickFind = new UnionQuickFind(n);
        // unionQuickFind.initializeArray();
        unionQuickFind.initializeArray(arr);
        unionQuickFind.displayArray();
        unionQuickFind.unionOperation(4, 3);
        unionQuickFind.unionOperation(3, 8);
        unionQuickFind.unionOperation(6, 5);
        unionQuickFind.unionOperation(9, 4);
        unionQuickFind.unionOperation(2, 1);
        unionQuickFind.unionOperation(8, 9);
        unionQuickFind.connected(5, 0);
        unionQuickFind.unionOperation(5, 0);
        unionQuickFind.connected(5, 0);
        unionQuickFind.unionOperation(7, 2);
        unionQuickFind.unionOperation(6, 1);
    }

}

Output:

INDEXES

{p q} -> 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 

{4 3} -> 0, 1, 2, 3, 3, 5, 6, 7, 8, 9, 

{3 8} -> 0, 1, 2, 8, 8, 5, 6, 7, 8, 9, 

{6 5} -> 0, 1, 2, 8, 8, 5, 5, 7, 8, 9, 

{9 4} -> 0, 1, 2, 8, 8, 5, 5, 7, 8, 8, 

{2 1} -> 0, 1, 1, 8, 8, 5, 5, 7, 8, 8, 

{8 9} -> Already Connected

{5 0} -> Not Connected

{5 0} -> 0, 1, 1, 8, 8, 0, 0, 7, 8, 8, 

{5 0} -> Already Connected

{7 2} -> 0, 1, 1, 8, 8, 0, 0, 1, 8, 8, 

{6 1} -> 1, 1, 1, 8, 8, 1, 1, 1, 8, 8,