一、基本操作：

1、Find：当且仅当两个元素属于相同的集合时，返回相同的名字

2、Union：将两个不相交的集合合并为一个不想交的集合。

应用：在等价关系中，判断两个元素之间是否有关系或者添加等价关系。

二、基本数据结构

1、Quick-Find实现

采用一个数组保存每个等价类的名字，这种实现下Find的复杂度为O(1)，而Union实现的复杂度为O(n)。

例如Union(i，j)：Union操作需要遍历整个数组，将所有为j的元素改为i。

1 public class ADTQuickFind { 2     private int[] id; 3     private int size; 4     public ADTQuickFind(int size){ 5         this.size = size; 6         id = new int[size]; 7         //初始化默认所有节点不联通 8         for(int i = 0; i < size; i++) 9             id[i] = i;10     }11 12     public int find(int p){13         //p的值出现异常14         if(p < 0 || p >= size)15             return  -1;16         return id[p];17     }18 19     public void Union(int p, int q){20         int pId = find(p);21         int qId = find(q);22         if(pId == qId)23             return;24         for(int i = 0; i < size; i++){25             if(id[i] == qId)26                 id[i] = pId;27 28         }29     }30 31     public boolean isRelated(int p, int q){32         return find(p) == find(q);33     }34 }

如果最开始所有元素都不连通，那么最多执行N-1次Union运算，此时所有的元素都在一个等价类中，总的时间复杂度为O(n2)。

如果Find运算比较多的情况下，存在Ω(n2)次Find运算，那么平均每次Find或者Union的时间复杂度为O(1)，但是如果Find的次数比较少，那么这种方法是不可以接受的。

2、Quick-Union实现

在数组中隐式地存储一个森林，每个数组对应的位置存储对应节点的父节点的编号，树根节点保存自己的编号。

Find：由于Find操作要求当且仅当两个元素在相同的集合时，作用在两个元素上的Find操作返回相同的名字。而返回元素的标记是什么并不重要，因此通过返回一个节点的根节点的编号代表节点所处等价类的编号。

Union：使一个节点的根指针指向另一棵树的根节点。

1 public class ADTQuickUnion { 2     int[] parent; 3     int size; 4     public ADTQuickUnion(int size){ 5         this.size = size; 6         parent = new int[size]; 7         for(int i = 0; i < size; i++) 8             parent[i] = i; 9     }10     public int find(int p){11         if(p < 0 || p >= size)12             return -1;   //出现异常值13         while(parent[p] != p)14             p = parent[p];15         return p;16     }17     public void union(int p, int q){18         int pId = find(p);19         int qId = find(q);20         if(pId == qId)21             return;22         parent[qId] = pId;23     }24     public boolean isRelated(int p, int q){25         return find(p) == find(q);26     }27 }

算法中执行Find操作花费的时间与节点的深度成正比，最坏情况下，会建立一个深度为N-1的树，使用一次Find的最坏情形运行时间为O(n)。

3、QuickUnionBetter实现

在Union操作中，将元素个数较少的树插到元素个数较多的树的根节点上。

1 public class ADTQuickUnionBetter { 2     private int[] parent; 3     private int[] mSize; 4     private int size; 5     public ADTQuickUnionBetter(int size){ 6         this.size = size; 7         parent = new int[size]; 8         mSize = new int[size]; 9         for(int i = 0; i < size; i++){10             parent[i] = i;11             mSize[i] = 1;12         }13     }14     public int find(int p){15         if(p < 0 || p >= size)16             return -1;  //表明出现异常值17         while(p != parent[p])18             p = parent[p];19         return p;20     }21     public void union(int p, int q){22         int pId = find(p);23         int qId = find(q);24         if(pId == qId)25             return;26         if(mSize[pId] < mSize[qId]){27             parent[pId] = qId;28             mSize[qId] = mSize[pId] + mSize[qId];29         }30         else{31             parent[qId] = pId;32             mSize[pId] = mSize[qId] + mSize[pId];33         }34     }35     public boolean isRelated(int p, int q){36         return find(p) == find(q);37     }38 }

可以证明，任何节点的深度不会超过log(n)，由于随着深度每次随着Union的结果而增大1时，该节点被置于节点数至少为原先两倍大的树上。

因此Find操作的时间复杂度为O(log(n))，连续M次操作的时间复杂度为O(MlogN)，平均时间得到证明为O(M)时间，为线性的。

4、Find中优化路径压缩优化路径压缩

1 public int find(int p){2     if(p < 0 || p >= size)3         return -1;  //异常值4     while(p != parent[p]){5         parent[p] = parent[parent[p]];6         p = parent[p];7     }8     return p;9 }