定义

等价关系

  • 【Definition】A relationR is defined on a set S if for every pair of elements (a, b), a, b ∈S, a R b is either true or false. If a R b is true, then we say that a is related to b.
  • 【Definition】A relation, ~, over a set, S, is said to be an equivalence relation over S iff it is symmetric, reflexive, and transitive over S.
  • 【Definition】Two members x and y of a set S are said to be in the same equivalence class iff x ~ y.

不相交集

Example: _S_1 = { 6, 7, 8, 10 }, _S_2 = { 1, 4, 9 }, _S_3 = { 2, 3, 5 }
image.png image.png image.png
指针由children到parents。

操作

Union(i, j)

Si∪Sj

image.png
Implementation1
image.png
Implementation2
假设数字是1到n，这样数字可以用作数组下标。
S [ element ] = the element’s parent
image.png
PS：这种Union不是最好的，有可能会增加树的高度。

Find(i)

找到含元素i的集合Sk

image.png

Smarter Ways to Do Union

按大小求并 | Union-by-Size
Lemma：若Union均按大小进行，则任何节点的深度均不会超过并查集 | The Disjoint Set - 图8。
image.png

具体操作方法是每个根的数组元素包含它的树的大小的负值，每执行一次Union时，要更新树的大小，新的大小为老的大小之和。通过这种方式，N次Union和M次Find的时间复杂度为并查集 | The Disjoint Set - 图10。

按高度（秩）求并 | Union-by-Height
这种方式求并同样可以保证所有的树深度最多是并查集 | The Disjoint Set - 图11。他可以使较浅的树成为较深的树的子树，并且只有在两棵树高度相等合并时树的高度才增加1。
具体操作方法是每个根的数组元素包含它的树的高度的负值，每执行一次Union时，要更新树的大小，新的大小为老的大小之和。

Smarter Way to Do Find

路径压缩 | Path Compression
从X到根的路径上的每一个节点，都使其父节点变成根。

  1. SetType  Find ( ElementType  X, DisjSet  S )
  2. {   ElementType  root,  trail,  lead;
  3.     for ( root = X; S[ root ] > 0; root = S[ root ] )
  4.         ;  /* find the root */
  5.     for ( trail = X; trail != root; trail = lead ) {
  6.        lead = S[ trail ] ;   
  7.        S[ trail ] = root ;   
  8.     }  /* collapsing */
  9.     return  root ;
  10. }
  1. SetType  Find ( ElementType  X, DisjSet  S ){
  2.     if ( S[ X ] <= 0 )    return  X;
  3.     else return  S[ X ] = Find( S[ X ], S );
  4. }

重要
路径压缩与按大小求并兼容，可以同时实现，而与按高度求并不兼容，因为压缩的过程改变了树的高度。