Union Found
1.Quick found
Data structure.
• Integer array id[] of size N.
• Interpretation: p and q are connected if they have the same id.
Find
Check if p and q have the same id.
Time complexity: O(1)
Union
To merge components containing p and q, change all entries with id[p] to id[q].
Time complexity: O(N)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
public class QuickFind{ private int[] id; } public QuickFind(int N){ id = new int[N]; for (int i = 0; i < N; i++) id[i] = I; //set id of each object to itself } public boolean find(int p, int q){ return id[p] == id[q]; } public void union(int p, int q){ int pid = id[p]; for (int i = 0; i < id.length; i++) if (id[i] == pid) id[i] = id[q]; } } |
2.Quick Union
Data structure.
• Integer array id[] of size N.
• Interpretation: id[i] is parent of i. • Root of i is id[id[id[…id[i]…]]].
Find
Check if p and q have the same root.
Time complexity: O(N)
Union
Set the id of q’s root to the id of p’s root.
Time complexity: O(N*)
In theory it should be less than quick find because we don’t need to go through the entire list.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public class QuickUnion { private int[] id; public QuickUnion(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 find(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; } } |
3.Weighted Quick Union
Data structure.
• Almost identical to quick-union.
• Maintain extra array sz[] to count number of elements
in the tree rooted at i.
Find
Check if p and q have the same root.
Time complexity: O(logN)
Union
• merge smaller tree into larger tree
• update the sz[] array.
Time complexity: O(logN*)
|
1 2 3 4 5 6 7 8 9 10 |
... if(size[i]<size[j]){ id[i]=j; size[j]+=size[i]; }else { id[j]=i; size[i]+=size[j]; } ... |
4.Weighted Quick Union with path compression
Path compression. Just after computing the root of i,
set the id of each examined node to root(i).
Standard implementation: add second loop to root() to set the id of each examined node to the root.
Simpler one-pass variant: make every other node in path point to its grandparent.
Data structure:
Using Path compression
Find
The same as QU
Time complexity: O(N+MlogN*)
Union
The same as QU
Time complexity: O(N+MlogN*)
|
1 2 3 4 5 6 7 |
public int root(int i){ while(i!=id[i]){ id[i]=id[id[i]]; i=id[i]; } return i; } |
One thought