相關(guān)概念

等價(jià)關(guān)系
若對于每一對元素(a, b), ，aRb或者為true或者為false，則稱在集合S上定義關(guān)
系（relation)R。如果aRb是true，則說a與b有關(guān)系。
等價(jià)關(guān)系（equivalence relation）是滿足下列三個(gè)性質(zhì)的關(guān)系R:
1.（自反性）對于所有的，aRa。
2.（對稱性）aRb當(dāng)且僅當(dāng)bRa。
3.（傳遞性）若aRb且bRc，則aRc。

比如<=不是等價(jià)關(guān)系，電氣連通性是一個(gè)等價(jià)關(guān)系

等價(jià)類
一個(gè)元素的等價(jià)類是S的一個(gè)子集，它包含所有與a有等價(jià)關(guān)系的元素。

為確定是否aRb，我們只需驗(yàn)證a和b是否都在同一個(gè)等價(jià)類中。

不相交集合的find/union算法
對于該等價(jià)類，一般有兩種操作。

1. find
   它返回包含給定元素的集合（即等價(jià)類）的名字
2. union

用于添加關(guān)系aRb

具體步驟：

• 首先檢查a和b是否在同一個(gè)等價(jià)類中
• 如果不在，則使用union操作，將含有a和b的兩個(gè)等價(jià)類合并成一個(gè)新的合并類

注：現(xiàn)已證明兩個(gè)操作不能同時(shí)以常數(shù)最壞情形運(yùn)行時(shí)間執(zhí)行。

基本數(shù)據(jù)結(jié)構(gòu)

使用樹表示每一個(gè)集合，根用來命名所在的集合。

// Process Init
public DisjSets(int numElements) {
  s = new int[numElments];
  for(int i=0; i<s.length; i++) 
    s[i] = -1;
} 
// Process Union
public void union(int root1, int root2) {
  s[root2] = root1;
}
// Process Find
public int find(int x) {
  if(s[x]<0)
    return x;
  else
    return find(s[x]);
}

平均情形分析依賴于如何定義平均（對于union操作涉及大樹的概率）。由于union操作隨機(jī)，因此最壞情況下會(huì)讓樹高呈線性增長。

按大小求并

對于union操作，總讓較小的樹成為較大的樹的子樹。

那么任何節(jié)點(diǎn)的深度均不會(huì)超過logN

實(shí)現(xiàn)
讓每個(gè)根的數(shù)組元素包含它的樹的大小的負(fù)值，則不需要額外的空間。

按高度求并

跟蹤每棵樹的高度，對于union操作，使得淺的樹成為深的樹的子樹。

同樣保證所有的樹的深度最多是logN

實(shí)現(xiàn)
讓每個(gè)根的數(shù)組元素包含它的樹的高度的負(fù)值-1，則不需要額外的空間

已證明，若使用按大小/高度求并，則連續(xù)M次運(yùn)算（union/find）需要O(M)平均時(shí)間，但O(MlogN)的最壞情況還是可能相當(dāng)容易和自然發(fā)生的。

路徑壓縮

對于find(x)操作，從x到根的路徑上的每一個(gè)節(jié)點(diǎn)都使其指向該樹的根。

public int find(int x) {
  if(s[x]<0)
    return x;
  else
    return s[x] = find(s[x]);
}

路徑壓縮與按大小求并兼容，而不完全與按高度求并兼容（路徑壓縮可以改變樹的高度）。針對于按高度求并，我們不重新計(jì)算高度，而將其作為秩，成為按秩求并。

已證明，對于兩種求并方法（按大小求并/按秩求并），路徑壓縮都能夠顯著地減少最壞情況運(yùn)行時(shí)間。

應(yīng)用

生成迷宮