之前我们介绍了并查集，但是我们可以进行简化，使得并查集的效率更高

原先并查集的缺点

//原来的并查集代码
typedef struct {
    ElementType Data;
    int Parent;
} SetType;

int Find( SetType S[], ElementType X )
{ 
    int i;
    for ( i=0; i<MaxSize && S[i].Data!=X; i++ ) ;//最坏的情况，这里要将所有的元素查找一遍
    if ( i>=MaxSize ) return -1;
    for( ; S[i].Parent>=0; i=S[i].Parent ) ;
    return i;
}

优化

任何有限集合的（N个）元素都可以被一一映射为整数 0 ~ N–1

typedef int ElementType; /*默认元素可以用非负整数表示*/
typedef int SetName; /*默认用根结点的下标作为集合名称*/
typedef ElementType SetType[MaxSize];

SetName Find( SetType S, ElementType X )
{ /* 默认集合元素全部初始化为-1 */
    for ( ; S[X]>=0; X=S[X] ) ;
    return X;
} 

void Union( SetType S, SetName Root1, SetName Root2 )
{ /* 这里默认Root1和Root2是不同集合的根结点 */
    S[Root2] = Root1;
} 

按秩归并

为什么要按秩归并

按原本的归并方法，旧结点是归并到新结点上的，那么最坏的情况下就会如下

显然这样效率不高。因此集合的归并应该是小集合归并到大集合上。

集合的比较可以根据

1、 树的高度
2、 集合的规模

按秩归并后的代码

//树的高度
if ( S[Root2] < S[Root1] )
    S[Root1] = Root2;
else {
    if ( S[Root1]==S[Root2] ) S[Root1]--;
    S[Root2] = Root1;
}

//集合的规模
void Union( SetType S, SetName Root1, SetName Root2 )
{ 
    if ( S[Root2]<S[Root1] ){
        S[Root2] += S[Root1];
        S[Root1] = Root2;
    }
    else {
        S[Root1] += S[Root2];
        S[Root2] = Root1;
    }
}

路径压缩

SetName Find( SetType S, ElementType X )
{ 
if ( S[X] < 0 ) /* 找到集合的根 */
    return X;
else
    return S[X] = Find( S, S[X] );
}

return S[X] = Find( S, S[X] )有三个操作
1.先找到根；
2.把根变成 X 的父结点；
3.再返回根。

优化后的代码

#define MAXN 1000                  /* 集合最大元素个数 */
typedef int ElementType;           /* 默认元素可以用非负整数表示 */
typedef int SetName;               /* 默认用根结点的下标作为集合名称 */
typedef ElementType SetType[MAXN]; /* 假设集合元素下标从0开始 */

void Union( SetType S, SetName Root1, SetName Root2 )
{ /* 这里默认Root1和Root2是不同集合的根结点 */
    /* 保证小集合并入大集合 */
    if ( S[Root2] < S[Root1] ) { /* 如果集合2比较大 */
        S[Root2] += S[Root1];     /* 集合1并入集合2  */
        S[Root1] = Root2;
    }
    else {                         /* 如果集合1比较大 */
        S[Root1] += S[Root2];     /* 集合2并入集合1  */
        S[Root2] = Root1;
    }
}

SetName Find( SetType S, ElementType X )
{ /* 默认集合元素全部初始化为-1 */
    if ( S[X] < 0 ) /* 找到集合的根 */
        return X;
    else
        return S[X] = Find( S, S[X] ); /* 路径压缩 */
}

文章永久链接：https://tech.souyunku.com/40762