Union-find approach - quick-union - jaredgorski.org

Back to notes

Union-find approach - quick-union

Keywords: union-find, quick-union, algorithms
Date:
  • The data structure for this approach is as follows:
    • integer array id[N]
      • N is equal to the number of objects in the disjoint set
        • each index of id[] corresponds to an object in the disjoint set
    • interpretation: id[i] is parent of i
    • root of i is id[id[id[...id[i]...]]]
id[10]{0, 1, 9, 4, 9, 6, 6, 7, 8, 9}

// root of `3` is `9` (`id[3]` is `4`, `id[4]` is `9`)
  • Find:
    • Check if p and q have the same root
  • Union:
    • To merge components containing p and q, set the id of p's root to the id of q's root

Example implementation

public class QuickUnionUF
{
  private int[] id;
  
  public 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;
  }
}

Problem: too slow

  • trees can get very tall
  • for each connected() (Find) operation, the array can be accessed as many as N times

Cost:

  • new: N
  • Union: N (including cost of finding roots)
  • Find: N

Backlinks: