Quick Find Algoritması

Giriş
O (N ^2) bir algoritmadır. Çünkü önce N tane union sonra da N tane find işlemi yapılır.

Algoritma
Algoritma şöyledir. parent dizisi bir elemanın en üst atasını saklar.

// Naive implementation of find
int find(int parent[], int i)
{
  if (parent[i] == -1)
    return i;
  return find(parent, parent[i]);
}

// Naive implementation of union()
void Union(int parent[], int x, int y)
{
  int xset = find(parent, x);
  int yset = find(parent, y);
  parent[xset] = yset;
}

Union işlemi için bir uyarının açıklaması şöyle

"And I mentioned that a lot of us would get us wrong. The mistake we might make is to put ID of P here rather than first picking out, that value. And you can think about the implications of that. That's an insidious bug."

Elimizde şöyle bir kod olsun. Union metodunda p'nin en üst atasını alıp bir yerde saklamak gerekir. Yoksa diziyi dolaşırken en üst atanın değerini değiştiği için kaybedebiliriz.

public class QuickFindUF {
  private int[] id;

  public QuickFindUF(int N) {
    id = new int[N];
    for(int i = 0; i < N; i++) {
       id[i] = i;
    }
  }

  public boolean Connected(int p, int q) {
    return id[p] == id[q];
  }

  public void Union (int p, int q) {
    int pid = id[p];
    int qid = id[q];
    for (int i = 0; i < id.length; i++) {
      if (id[i] == pid) { //"id[i] == id[p]" is not correct! Why?
        id[i] = qid;
      }
    }
  }
}

Union
Union çağrısı x'in en üst atasını y yap anlamına gelir.

Union işlemi sonunda elimize şöyle bir yapı geçer.

Let there be 4 elements 0, 1, 2, 3

Initially all elements are single element subsets.
0 1 2 3 

Do Union(0, 1)
   1   2   3  
  /
 0

Do Union(1, 2)
     2   3   
    /
   1
 /
0

Do Union(2, 3)
         3    
        /
      2
     /
   1
 /
0

Union By Rank
Bu algoritma "union by rank" ve "path compression" yöntemkleri ile iyileştirilebilir. Bu yöntemleri anlamadım. "union by rank" şöyle yaparız.

Let us see the above example with union by rank
Initially all elements are single element subsets.
0 1 2 3 

Do Union(0, 1)
   1   2   3  
  /
 0

Do Union(1, 2)
   1    3
 /  \
0    2

Do Union(2, 3)
    1    
 /  |  \
0   2   3

Path Compression
"path compression" ile şöyle yaparız.

Let the subset {0, 1, .. 9} be represented as below and find() is called
for element 3.
              9
         /    |    \  
        4     5      6
     /     \        /  \
    0        3     7    8
            /  \
           1    2  

When find() is called for 3, we traverse up and find 9 as representative
of this subset. With path compression, we also make 3 as child of 9 so 
that when find() is called next time for 1, 2 or 3, the path to root is 
reduced.

               9
         /    /  \    \
        4    5    6     3 
     /           /  \   /  \
    0           7    8  1   2