并查集详细介绍

2020-07-16 Algorithm Structure

并查集 Union-Find 算法，顾名思义，用作合并集合、查找集合元素，通常用来解决图论中动态连通性问题，当然也包括了分类。

这里详细介绍基本概念。

简介

union find nodes

用于解决一些常见的元素分组问题，其基本概念就是将集合中的某个元素来代表这个集合，该元素称为集合的代表元，其它元素组织成以代表元为根的树形结构，在实现时通过数组表示。

其包含了两个基本操作：

  • 合并 Union，将两个不相交集合合并为一个集合。
  • 查询 Find，判断两个元素是否属于一个集合。

例如有如下几个元素，开始都各自指向自己，也就表示彼此互不相连。

union find init

通过一系列的合并操作之后，有如下的 A H 两个集合 (通过根标识某个集合)，然后对两个集合再次执行合并操作，那么得到的结果如下。

union find merge

也就是在 A H 连通之后，两个集合下面所有节点都有相同根节点，属于相同集合。

实现

如上所述，实现时一般通过数组表示，每个元素通过 parent[x] 标识 x 的父节点，如果是根节点，那么 parent[x]=x ，也就是指向自己。查找某个元素 x 所属集合，那么就可以沿着 parent[x] 一直向上查找，直到根节点。

判断两个元素是否属于同一集合，只需要看代表它们的根元素是否相同即可，所以，其实现基本如下。

int parent[NUM];

// 初始化时将各个节点指向自己
void init(int n)
{
	for (int i = 0; i < n; i++)
		parent[i] = i;
}

// 将两个元素所在集合合并为一个集合
void union(int p, int q)
{
	int root_p = find(p);
	int root_q = find(q);
	if (root_p == root_q)
		return;
	parent[root_p] = root_q;
	// parent[root_q] = root_p; // 两者是等价的
}

// 返回某个节点的代表元(根节点)
int find(int x)
{
	while (parent[x] != x)
		x = parent[x];
	return x;
}

// 判断两个节点是否是一个集合
int is_connected(int p, int q)
{
	return find(p) == find(q);
}

优化

接口最终都会调用 find() 方法，该方法就是从某个节点向上遍历到树根，那么其时间复杂度就是树的高度，对于平衡二叉树一般是 logN，而最坏可能会退化为链表，也就是 N 。

union find unbalance

左侧已经降级为链表，而右侧几乎降级为链表。

维持平衡

不平衡的过程发生在执行 union() 操作时，如上，如果在建立链接时，始终以固定方式链接，那么就可能会逐渐导致不平衡。

union find rank union

解决方法是，增加一个根节点的权重标识，将权重低的连接到权重高的节点上，这样可以保证树的基本平衡生长。

int rank[NUM];
int parent[NUM];

void union(int p, int q)
{
	int root_p, root_q;

	root_p = union_find(uf, p);
	root_q = union_find(uf, q);
	if (root_p == root_q)
		return;

	// 将小的树添加到大的树下面
	if (rank[root_p] > rank[root_q]) {
		parent[root_q] = root_p;
		rank[root_p] += rank[root_q];
	} else {
		parent[root_p] = root_q;
		rank[root_q] += rank[root_p];
	}
}

初始化时，将 rank 都设置为 1 ，每次合并再更新对应的权重值。

路径压缩

这里会进一步压缩树的高度，将属于某个根节点的节点都直接连接到根节点下面，那么查找将会直接变为 O(1)。这一步可以在查找时添加，第一次查找时耗时可能保持不变，后续的查找则会极大优化。

union find path compression

如下是具体实现。

int find(int x)
{
	while (parent[x] != x) {
		parent[x] = parent[parent[x]];
		x = parent[x];
	}
	return x;
}

也就是每次查找时，额外增加压缩，那么下次再查询就可以极大增加效率。

其它

在实现时有几种表示方法：A) 使用结构体，通过指针进行维护；B) 直接使用数组。注意，在具体实现时，可以发现，对于通过 find() 进行的路径压缩，两种实现是不同的，在不同的场景下可以进行选择，这里就不再统一了。

struct union_find {
	int rank;
	struct union_find *parent;
	uintptr_t value;
};

struct union_find *union_create(uintptr_t value)
{
	struct union_find *uf;

	uf = malloc(sizeof(*uf));
	if (uf == NULL)
		return NULL;

	uf->rank = 1;
	uf->parent = NULL;
	uf->value = value;

	return uf;
}

struct union_find *union_find_item(struct union_find *item)
{
	struct union_find *orig;

	if (item == NULL)
		return NULL;

	orig = item;
	while (item->parent != NULL)
		item = item->parent;
	if (item != orig->parent && item != orig)
		orig->parent = item; // path compression

	return item;
}

struct union_find *union_merge(struct union_find *p, struct union_find *q)
{
	struct union_find *root_p, *root_q, *root_new;

	root_p = union_find_item(p);
	root_q = union_find_item(q);

	root_new = root_p;
	if (root_p != root_q) {
		if (root_p->rank > root_q->rank) { // merge by rank
			root_q->parent = root_p;
			root_p->rank++;
		} else {
			root_p->parent = root_q;
			root_q->rank++;
			root_new = root_q;
		}
	}

	return root_new;
}