UNION-FIND ALGORITHMS

UNION-FIND ALGORITHMS

A union-find algorithm is an algorithm that performs two useful operations on such a data structure: Find: Determine which group a particular element is in.
Union: Combine or merge two groups into a single group

*Quick-find solution to connectivity problem*

Sample Program implemented in java:

public class QuickF 
  { public static void main(String[] args) 
    { int N = Integer.parseInt(args[0]); 
      int id[] = new int[N]; 
      for (int i = 0; i < N ; i++) id[i] = i; 
      for( In.init(); !In.empty(); ) 
        { int p = In.getInt(), q = In.getInt(); 
          int t = id[p]; 
          if (t == id[q]) continue; 
          for (int i = 0;i<N;i++) 
            if (id[i] == t) id[i] = id[q]; 
          Out.println(" " +p+""+q); 
        } 
    } 
  } 

The program above is an implementation of a simple algorithm called the quick-find algorithm that solves the connectivity problem.

Example of quick find (slow union)

This sequence depicts the contents of the id array after each of the pairs at left is processed by the quick-find algorithm Shaded entries are those that change for the union operation. When we process the pair pq, we change all entries with the value id[p] to have the value id[q].

The quick-find algorithm executes at least MN instructions to solve a connectivity problem with N objects that involves M union operations.
For each of the M union operations, we iterate the for loop N times. Each iteration requires at least one instruction (if only to check whether the loop is finished). 

Tree representation of quick find

The connections in these figures do not necessarily represent the connections in the input. For example, the structure at the bottom has the connection 1-7, which is not in the input, but which is made because of the string of connections 7-3-4-9-5-6-1.

 

 The next algorithm that we consider is a complementary method called the quick-union algorithm. It is based on the same data structure "an array indexed by object names” but it uses a different interpretation of the values that leads to more complex abstract structures. Each object has a link to another object in the same set, in a structure with no cycles. To determine whether two objects are in the same set, we follow links for each until we reach an object that has a link to itself. The objects are in the same set if and only if this process leads them to the same object. If they are not in the same set, we wind up at different objects (which have links to themselves). To form the union, then, we just link one to the other to perform the union operation; hence the name quick union.

Tree representation of quick union

This figure is a graphical representation of the example in  Tree representation of quick find. We draw a line from object i to object id[i].

Example of quick union (not-too-quick find)

This sequence depicts the contents of the id array after each of the pairs at left are processed by the quick-union algorithm. Shaded entries are those that change for the union operation (just one per operation). When we process the pair p q, we follow links from p to get an entry i with id[i] == i; then, we follow links from q to get an entry j with id[j] == j; then, if i and j differ, we set id[i] = id[j]. For the find operation for the pair 5-8 (final line), i takes on the values 5 6901, and j takes on the values 801.

Here is the link for the union-find algorithms. all discussions are presented well. it includes all visual representation of the said algorithm. I've also searched the sample code of an algorithm. This is very helpful for our future projects. Have a nice long read!! ^_^

http://www.risc.jku.at/people/ckoutsch/stuff/e_algorithms.html
http://flylib.com/books/en/3.55.1.18/1/