上一篇文章，简单介绍了并查集。

这篇文章，介绍一下并查集的改进以及优化。

1. find函数的优化（路径压缩）
   
   因为并查集的merge操作：

void merge(int a, int b) {  	//先找到两个元素对应的根对应的元素   	int fa = find(a);   	int fb = find(b);  	if(fa==fb) return;  	else f[fa]=fb;

这个操作会有什么效率问题呢?举例说明：

当我们初始化以后，每个节点都是自己的父节点，比如下面这样：

然后我们进行合并操作。

执行merge(1,2)后，f[1]=2后，

如果我们继续合并merge(1,3)，从1找到2后，变成f[2]=3，变成下面这样：

再来一个新元素4，merge(1,4)，然后从1找到3，f[3]=4，变成下面这样：

然后就会发现一个问题，按照这种方式下去，就会形成“一字长蛇阵”了，有什么危害呢？危害就是随着链越来越长，寻找根节点变的越来越复杂。

为了解决这个问题，我们使用路径压缩方法。

根据上面的例子，我们只关心 某个元素的根节点是什么，所以，我们希望“直接找到根节点”。变成下面这样：

“把沿途的每个节点的父节点都设为根节点”

参考代码：

int find(int x)  {      if(x == fa[x])          return x;      else{          fa[x] = find(fa[x]);        //父节点设为根节点          return fa[x];         //返回父节点      }  }

上面的代码可以解释为下面这个过程，

假如我们当前过程是 1—>2—>3。当前新节点是4，我们执行merge(1,4)操作，也就是我们要先通过find函数找到1的根节点。

find(1):          因为fa[1]=2，所以if不成立，执行else          fa[1]=find(fa[1])                          因为有find函数，继续递归，fa[1]=2,所以执行的是find(2)                             find(2):         因为fa[2]=3，所以if不成立，执行else         fa[2]=find(fa[2])                      因为有find函数，继续递归，fa[2]=3,所以执行的是find(3)  find(3):         因为fa[3]=3,if成立，return 3         此时回到find(2)函数中，fa[2]=3(本来就等于3，没有什么好说的)，然后继续return fa[2],         回到find(1)中，此时fa[1]=fa[2]=3,也就是，我们把1直接指向了3，3是1的直接父节点。

上面代码经常写成三目表达式形式：

int find(int x){      return x == fa[x] ? x : (fa[x] = find(fa[x]));}

     2.merge函数的优化（加权标记法）

场景：假设已经有下面的图了，我们想把 ‘节点1’ 加入到这个图中：

这个时候，是让5成为1的父节点，还是让1成为5的父节点呢？

答案很简单，那就是让5成为1的父节点，为什么呢？

如果让1成为5父节点，相当于把5的深度又加深了一层，这个每个节点到根节点的距离又增加了，虽然我们前面已经有了路径压缩，但是路径压缩也会耗费时间。

如果我们把5设为1的父节点，这个时候，整个树形结构没有增加深度，寻找根节点的距离没有增加。

结论：在合并过程中，将简单的树往复杂的树上合并。

方法：

1.首先我们定义一个数组rank，然后将树中所有节点都增设一个权值，用以表示该节点所在树中的高度（比如用rank[x]=3表示 x 节点所在树的高度为3）。

2.一开始，把所有元素的rank（秩）设为1。

3.合并时比较两个根节点，把rank较小者往较大者上合并。（如果rank[x] < rank[y]，则令fa[x] = y；否则令fa[y] = x。）

比如下面这张图：

我们对比两个图的根节点，发现rank(5)>rank(7)，所以让fa[7]=5（让 节点7 认 节点5 做爹！）

然后就会变成下面这样：

可以看出，本来两颗树的最高高度是3，合并后的最高高度还是3，也就是达到了我们的目的。如果执行fa[5]=7，那么会让合并后的树的高度又增加一层，这样便增加了寻找根节点的路径。

实现过程：

加权标记法的核心在于对rank数组的逻辑控制，其主要的情况有：

1、如果rank[x] < rank[y]，则令fa[x] = y；

2、如果rank[x] == rank[y]，则可任意指定上级；

3、如果rank[x] > rank[y]，则令fa[y] = x；

代码实现过程，首先是初始化，要加入一个数组用来记录层次

void init(int n)  {      for (int i = 1; i <= n; ++i)      {          fa[i] = i;          rank[i] = 1;      }  }

然后我们修改merge函数

void merge(int x,int y) {  	x=find(x);							//寻找 x的根节点   	y=find(y);							//寻找 y的根节点   	if(x==y) return ;					//如果 x和 y的根节点一致，说明他们共属同一集合，则不需要合并，直接返回；否则，执行下面的逻辑  	if(rank[x]>rank[y]) 				//如果 x的高度大于 y，则令 y的上级为 x  		fa[y]=x;	  	else {								  		if(rank[x]==rank[y]) 		   //如果 x的高度和 y的高度相同，则令 y的高度加1  			rank[y]++;	  		fa[x]=y;						//让 x的上级为 y  	}  }

缺点：

虽然上述操作可以很大程度上简化合并操作，但是因为引入了新数组，所以导致了额外的空间开销。

(adsbygoogle = window.adsbygoogle || []).push({});