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

Back to notes

Union-find approach - quick-find

Keywords: union-find, quick-find, 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
      • each value in id[] denotes the root/representative element of the set/component containing that particular object
    • interpretation: p and q are connected if and only if they have the same id
id[10]{0, 1, 1, 8, 8, 0, 0, 1, 8, 8}

// connected sets:
//  {0, 5, 6}
//  {1, 2, 7}
//  {3, 4, 8, 9}
  • Find:
    • Check if p and q have the same id
  • Union:
    • To merge components containing p and q, change all entries whose id == id[p] to id[q]

Example implementation

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] = qid;
  }
}

Problem: too slow (algorithm is quadratic)

  • for each new and union() operation, the array is accessed N times (the for loops)
    • we only use init() once, but union() is certainly too expensive:
      • N^2 array accesses are required to execute N union commands on N objects

Cost:

  • new: N
  • Union: N
  • Find: 1

Backlinks: