[数据结构与算法]【数据结构】并查集

参考博客

并查集1
并查集2
算法学习笔记(1)：并查集

并查集（Union-Find Set）

?? 也叫 Disjoint Set，由 Bernard A. Galler和Michael J. Fischer 在1964年提出，是一种树形数据结构，多用于处理一些不相交集合（disjoint sets）的合并与查询问题，可快速判断出两个元素是否属于同一集合/联通。

• 查找(Find)：查询两个元素是否在同一个集合中；
• 合并(Union)：把两个不相交的集合合并为一个集合。

1. 初始化

??初始情况下各节点的所在集合都只有自身，所以各节点的父节点都是自己。

void init(){
	for(int i = 0; i < maxn; i++)
		parent[i] = i;
}

2. 查找

??查找节点$x$所在集合/树的根节点。若两节点的根节点相同，则这两节点属于同一集合/同一棵树。

int find(int x){
	// 简写方式 
	// return parent[x] == x ? x : find(parent[x]);
	if(parent[x] == x) 
		return x;
	else
		return find(parent[x]);
}

3. 合并

??把节点$i$和节点$j$合并到同一个集合/树。

void union(int i, int j){ 
	int iroot = find(i);
	int jroot = find(j);
	if(iroot == jroot) // i,j属于同一棵树，不用合并
		return;
	// 把 i合并到 j所在树中
	parent[iroot] = jroot;	
} 

4. 优化

4.1 路径压缩

??通过降低树的高度来提高find函数的查询速度，即在find(x)执行过程中，将沿途遍历的节点直接与根节点连接。由于路径压缩是在查询时进行的，所以树结构仍可能十分复杂。

int find(int x){
	// 带压缩的简化写法 
	// return parent[x] == x ? x : (parent[x] = find(parent[x])); 
	if(parent[x] == x) return x;
	else{
		parent[x] = find(parent[x]); // 压缩路径，父节点设为根节点 
		return parent[x];
	}
}

4.2 按秩合并

??秩（rank）可以理解为树的高度，在节点合并时将秩小的树合并到秩大的树。

void union(int i, int j){ 
	// 按秩合并
	int iroot = find(i);
	int jroot = find(j);
	if(iroot == jroot) return;
	if(rank[i] <= rank[j])
		parent[iroot] = jroot;
	else
		parent[jroot] = iroot;
	// 若 i，j所在树深度不等，合并后树深度不变
	// 若 i，j所在树深度相等，则被合并的树深度需加 1 
	if(rank[i] == rank[j])
		++rank[jroot];
}

5. 算法复杂度

• 无优化：并查集每次操作的最差时间复杂度为$O(n)$ ，即树退化为链表。
• 仅采用路径压缩优化：每次操作的最差时间复杂度为$O(1+lo{g}_{2+f/n}n)$ ，这个值比$O(lo{g}_{2?n})$ 小，其中$f$为查找次数。
• 当仅使用按秩合并优化：每次操作的最差时间复杂度为$O(lo{g}_{2?n})$。
• 当同时使用路径压缩和按秩合并优化时：每次操作的最差时间复杂度为$O(lo{g}_{?}?n)$，其中$lo{g}_{?}?n$是Iterated Logarithm函数，实际使用中，它的值不超过 5，这也就是说每次操作的实际复杂度只有$O(1)$ 。

6. 代码

??以下图为例，合并节点（2,9）（4,9）（3,4）（5,6）。

#include <iostream>
using namespace std;
const int maxn = 10;

int parent[maxn]; // 存放各节点的父元素 
int rnk[maxn];    // 秩存放树的高度(rank与系统变量重名) 
 
void init(){
	for(int i = 0; i < maxn; i++){ 
		parent[i] = i;
		rnk[i] = 0;
	} 
}

int find(int x){
	// 不带压缩、带压缩的简化写法 
	// return parent[x] == x ? x : find(parent[x]);
	// return parent[x] == x ? x : (parent[x] = find(parent[x])); 
	if(parent[x] == x) return x;
	else{
		parent[x] = find(parent[x]); // 压缩路径，父节点直接连到根节点 
		return parent[x];
	}
}

void merge(int i, int j){
	// 不使用按秩合并 
	// parent[find(i)] = find(j); // 把 i合并到 j所在树中 
	// 按秩合并
	int iroot = find(i);
	int jroot = find(j);
	if(iroot == jroot) return;
	if(rnk[i] <= rnk[j])
		parent[iroot] = jroot;
	else
		parent[jroot] = iroot;
	// 若 i，j所在树深度不等，合并后树深度不变
	// 若 i，j所在树深度相等，则被合并的树深度加 1
	if(rnk[i] == rnk[j])
		++rnk[jroot];
} 

int main(){
	init();
	
	merge(2, 9);
	merge(4, 9);
	merge(3, 4);
	merge(5, 6);
	 
	// 判断 3 和 2 是否连通
    if(find(3) == find(2))
        cout << "3 和 2 连通.\n";
    else
        cout << "3 和 2 不连通.\n";
        
	return 0;
}

与50位技术专家面对面

20年技术见证，附赠技术全景图