Union Find

Union Find algorithm uses array structure to link components together


Appendix


Term Definition

  • Component: If the root of node p and q are same, they belongs to same component.

  • Node depth: The number of edges between node and root.

  • Tree height: The number of edges in the longest path in the tree.


Quick Find

In quick find, if we want to link p and q, we directly change all items whose component is also p to q.

public class quickfind{
  public Item[] id;
  public int count;
  public quickunion(Item[] id){
    this.id = id;
    this.count = id.length;
  }

  public static int find(int i){
    return id[i];
  }

  public static void union(int p, int q){
    int pid = find(p);
    int qid = find(q);

    if(qid == qid) return;
    for(int i = 0 ; i < id.length; i++){
      if(pid == id[i]) id[i] = qid;
    }
    count--;
  }
}

Quick Union

In quick union, if we want to link p and q, Generally we always connect p to q, Specifically we always connect p’s root to q’s root

public class quickunion<Item>{
  public Item[] id;
  public int count;
  public quickunion(Item[] id){
    this.id = id;
    this.count = id.length;
  }

  public static int find(int i){
    while(id[i] != i){
      i = id[i];
    }
    return i;
  }

  public static void union(int p, int q){
    int pid = find(p);
    int qid = find(q);
    if(pid == qid) return;
    id[pid] = qid;
    count--;
  }
}


Weighted Union

Compare to Quick Union, we always link p’s root to q’s root no matter how big is the tree which p belongs to. The optimization is linking small tree to large tree

public class Weightedunion{
  public Item[] id;
  public int count;
  public int size[];
  public quickunion(Item[] id){
    this.id = id;
    this.count = id.length;
    for(int i = 0; i < id.length; i++){
      this.size[i] = 1;
    }
  }

  public static int find(int i){
    while(id[i] != i){
      i = id[i];
    }
    return i;
  }

  public static void union(int p, int q){
    int pid = find(p);
    int qid = find(q);
    if(pid == qid) return;
    if(size[p] < size[q]){
      id[pid] = qid;
      size[q] = size[q]+size[p];
    }else{
      id[qid] = pid;
      size[p] = size[p]+size[q];
    }
    count--;
  }
}

Weighted Union with Path Compression

Trying to make the tree to be more balance, which decrease the hight of the tree.The method is trying to linked all the nodes along the path to the root directly to the root.

The goal of find is to find the root of a node, but along the finding journey, we optimize the algorithm by compress the path

public class Weightedunion{
  public Item[] id;
  public int count;
  public int size[];
  public quickunion(Item[] id){
    this.id = id;
    this.count = id.length;
    for(int i = 0; i < id.length; i++){
      this.size[i] = 1;
    }
  }

  public static int find(int i){
    int k, j, r;
    r = i; //r save the root of i
    while(id[r] != r){
      r = id[r];
    }

    k = i; //k is the count variable during iteration
    while(id[k] != k){
      j = id[k] //j save the parent of k
      id[k] = r //make k's parent directly to r(root)
      k = j //update the count variable, I mean start to deal with next node
    }

    return r;

  }

  public static void union(int p, int q){
    int pid = find(p);
    int qid = find(q);
    if(pid == qid) return;
    if(size[p] < size[q]){
      id[pid] = qid;
      size[q] = size[q]+size[p];
    }else{
      id[qid] = pid;
      size[p] = size[p]+size[q];
    }
    count--;
  }
}