并查集

Love The Way You Lie 2022-04-17 02:27 379阅读 0赞

### 森林: ###

森林是由若干棵互不相交的树组成,两棵树分别独立,没有交集

![20181112082744488.png][]

### 并查集: ###

并查集的结构和森林十分相似,是用于解决不相交集合如下若干几种操作的统称

### 1.MAKE\_SET(x):初始化操作,建立一个只包含元素x的集合 ###

### 2.UNION(x,y):合并操作,将包含x和y的集合合并成一个新集合 ###

### 3.FIND\_SET(x):查询操作,计算x所在集合 ###

(一般用于求不相交集合的并集)

通常我们用有根树来表示集合,树中的每个结点对应集合中的一个成员

每个成员有一条指向父节点的边,整个有根树通过这些指向父节点的边来维护

**每棵树的根就是这个集合的代表,并且这个代表的父节点就是它自己**

### 基本操作: ###

初始化:

对每个元素都建立一个只包含该元素自己的集合,这意味着每个成员都是自身所在集合的代表,只需将父节点设为它自己

查询:

在不相交的森林中,并查集的查询操作,指的是查出指定元素所在有根树的根节点是谁

合并:

查找到代表元素,将其中一个根节点的父亲设置成另外一个根节点,如下图演示,我们完成了合并操作

![20181112084256857.png][]

集合的传递性(如果a和b同属一个集合,b和c同属一个集合,那么a和c也同属一个集合)

### 相应算法的实现: ###

创建一个并查集:

class DDJSSet {
    private:
    	int* father;   //用来保存每个结点的父结点
    	int* rank;     //用来保存每个结点的秩
    public:
    	DDJSSet(int size) {
    		father = new int[size];
    		rank = new int[size];
    		for (int i = 0; i < size; ++i) {
    			father[i] = i;   //初始化时,将每个结点的父节点指向它自己
    			rank[i] = 0;
    		}
    	}
    
    	~DDJSSet() {
    		delete[] father;
    		delete[] rank;
    	}
    };

查询操作:

1.寻找当前结点的父结点

2.如果父节点是它本身,那么该点就是父节点,如果不是,则返回步骤1继续查找

合并操作:

1.分别获得传入的两个结点所在树的根结点

2.如果两个数所在根节点相同,说明他们在同一棵树上,返回false,结束合并操作

3,如果两个根节点不同,则将一个根节点的父节点指向另一个根节点,返回true结束操作

但是这样做会带来一些问题:我们任选一个结点指向一棵树的父结点,可能会导致一子棵树过长,最终整个并查集退化成一个链表,降低了查找效率,我们可以通过树的高度来判断连接顺序,将高度低的树的根节点连接到高度高的树的根节点

按秩合并:

1.利用一个数组保存每个结点所在树的高度的(初始化为0)

2.获得传入结点的树的根节点

3.若两个根节点不同,比较他们的高度

4.将高度低的树的父节点指向高度高的树的根结点

5.更新合并后的根节点的高度,返回

/*合并操作*/
    	bool merge(int node1, int node2) {
    		int ancestor1 = find_set(node1);
    		int ancestor2 = find_set(node2);
    		if (ancestor1 != ancestor2) {
    			if (rank[ancestor1] > rank[ancestor2]) {
    				swap(ancestor1, ancestor2);
    			}
    			father[ancestor1] = ancestor2;
    			rank[ancestor2] = max(rank[ancestor2], rank[ancestor1] + 1);   //更新秩
    
    			return true;
    		}
    		return false;
    	}

### 路径压缩: ###

![20181112092153616.png][]

如上图所示,如果我们把每一个子节点都指向这个并查集的根节点,这样会大大地降低查找效率

在执行寻找根节点的函数中,我们稍作修改,将查找路径上的所有结点都指向最终查找到的根节点

/*路径压缩算法*/
    	int find_set(int node) {
    		if (father[node] != node) {
    			father[node] = find_set(father[node]);
    		}
    		return father[node];
    	}

### 整体代码: ###

#include <iostream>
    #include <algorithm>
    using namespace std;
    
    class zDisjointSet {
    private:
    	int* father;
    	int* rank;
    public:
    	zDisjointSet(int size) {
    		father = new int[size];
    		rank = new int[size];
    		for (int i = 0; i < size; ++i) {
    			father[i] = i;
    			rank[i] = 0;
    		}
    	}
    	~zDisjointSet() {
    		delete[] father;
    		delete[] rank;
    	}
    
    	/*路径压缩算法*/
    	int find_set(int node) {
    		if (father[node] != node) {
    			father[node] = find_set(father[node]);
    		}
    		return father[node];
    	}
    
    	/*合并操作*/
    	bool merge(int node1, int node2) {
    		int ancestor1 = find_set(node1);
    		int ancestor2 = find_set(node2);
    		if (ancestor1 != ancestor2) {
    			if (rank[ancestor1] > rank[ancestor2]) {
    				swap(ancestor1, ancestor2);
    			}
    			father[ancestor1] = ancestor2;
    			rank[ancestor2] = max(rank[ancestor2], rank[ancestor1] + 1);   //更新秩
    
    			return true;
    		}
    		return false;
    	}
    };

###  ###

[20181112082744488.png]: /images/20220417/d70be596421a4b568afd6e9725214a28.png
[20181112084256857.png]: /images/20220417/b44ac4ba51d649ecabd183c2e3e08ceb.png
[20181112092153616.png]: /images/20220417/f6818ee84d424352b465bfc053c318b1.png