并查集 - 算法 | Lin's Blog = 凛

# 概述

并查集使用的是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。

比如让你求两个人是否间接认识，两个地点之间是否有至少一条路径。上面的例子其实都可以抽象为联通性问题。即如果两个点联通，那么这两个点就有至少一条路径能够将其连接起来。值得注意的是，并查集只能回答 “联通与否”，而不能回答诸如 “具体的联通路径是什么”。如果要回答 “具体的联通路径是什么” 这个问题，则需要借助其他算法，比如广度优先遍历。

# 形象解释

比如有两个司令。司令下有若干军长，军长下有若干师长。。

# 判断两个节点是否联通

我们如何判断某两个师长是否归同一个司令管呢（连通性）？
军长连通示意

很简单，我们顺着师长，往上找，找到司令。如果两个师长找到的是同一个司令，那么两个人就归同一个司令管。（假设这两人级别比司令低）
如果我让你判断两个士兵是否归同一个师长管，也可以向上搜索到师长，如果搜索到的两个师长是同一个，那就说明这两个士兵归同一师长管。（假设这两人级别比师长低）
代码上我们可以用 parent [x] = y 表示 x 的 parent 是 y，通过不断沿着搜索 parent 搜索找到 root，然后比较 root 是否相同即可得出结论。这里的 root 实际上就是上文提到的集合代表。

之所以使用 parent 存储每个节点的父节点，而不是使用 children 存储每个节点的子节点是因为 “我们需要找到某个元素的代表（也就是根）”

这个不断往上找的操作，我们一般称为 find，使用 ta 我们可以很容易地求出两个节点是否连通。

# 合并两个连通区域

如图有两个司令：
合并司令连通图
我们将其合并为一个联通域，最简单的方式就是直接将其中一个司令指向另外一个即可：
合并司令连通图2
以上就是三个核心 API find ， connnected 和 union ，的形象化解释，下面我们来看下代码实现。

# 核心 API

并查集（Union-find Algorithm）定义了两个用于此数据结构的操作：

Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
Union：将两个子集合并成同一个集合。

首先我们初始化每一个点都是一个连通域，类似下图：
并查集初始化序列
为了更加精确的定义这些方法，需要定义如何表示集合。一种常用的策略是为每个集合选定一个固定的元素，称为代表，以表示整个集合。接着，Find (x) 返回 x 所属集合的代表，而 Union 使用两个集合的代表作为参数进行合并。初始时，每个人的代表都是自己本身

这里的代表就是上面的 “司令”。

比如我们的 parent 长这个样子：

	{
	"0": "1",
	"1": "3",
	"2": "3",
	"4": "3",
	"3": "3"
	}

# find

假如我让你在上面的 parent 中找 0 的代表如何找？

首先，树的根在 parent 中满足 “parent [x] == x”。因此我们可以先找到 0 的父亲 parent [0] 也就是 1，接下来我们看 1 的父亲 parent [1] 发现是 3，因此它不是根，我们继续找 3 的父亲，发现是 3 本身。也就是说 3 就是我们要找的代表，我们返回 3 即可。

	//find 的过程，递归实现，并把沿途的所有结点都指向父节点
	private Data find(Data node) {
	Data father = fatherMap.get(node);
	if (father != node) {
	father = find(father);
	}
	fatherMap.put(node, father);
	return father;
	}

这里我在递归实现的 find 过程进行了路径的压缩，每次往上查找之后都会将树的高度降低到 2。

这有什么用呢？我们知道每次 find 都会从当前节点往上不断搜索，直到到达根节点，因此 find 的时间复杂度大致相等于节点的深度，树的高度如果不加控制则可能为节点数，因此 find 的时间复杂度可能会退化到 $O(n)$ 。而如果进行路径压缩，那么树的平均高度不会超过 $logn$ ，如果使用了路径压缩和下面要讲的按秩合并那么时间复杂度可以趋近 $O(1)$ ，具体证明略。不过给大家画了一个图来辅助大家理解。

注意是趋近 O (1)，准确来说是阿克曼函数的某个反函数。

路径压缩

极限情况下，每一个路径都会被压缩，这种情况下继续查找的时间复杂度就是 $O(1)$ 。
路径压缩1

# connected

判断两个节点的祖先是否相同，即是否连通

	// 判断是否是同一个代表节点
	public boolean isSameSet(Data a, Data b) {
	return find(a) == find(b);
	}

# union

将其中一个节点挂到另外一个节点的祖先上，这样两者祖先就一样了。也就是说，两个节点联通了。
对于如下的一个图：

如果我们将 0 和 7 进行一次合并。即 union(0, 7) ，则会发生如下过程。

找到 0 的根节点 3
找到 7 的根节点 6
将 6 指向 3。（为了使得合并之后的树尽可能平衡，一般选择将小树挂载到大树上面，下面的代码模板会体现这一点。3 的秩比 6 的秩大，这样更利于树的平衡，避免出现极端的情况）

按秩合并节点
上面讲的小树挂大树就是所谓的按秩合并。

	// 联合方法，把小节点接到大节点下面
	public void union(Data a, Data b) {
	if (a == null \|\| b == null) {
	return;
	}
	Data aHead = find(a);
	Data bHead = find(b);
	if (aHead != bHead) {
	Integer aSetSize = sizeMap.get(aHead);
	Integer bSetSize = sizeMap.get(bHead);
	if (aSetSize <= bSetSize) {
	fatherMap.put(aHead, bHead);
	sizeMap.put(bHead, aSetSize + bSetSize);
	} else {
	fatherMap.put(bHead, aHead);
	sizeMap.put(aHead, aSetSize + bSetSize);
	}
	}
	}

# 代码模板

	public class UnionFind {
	public static class Data {
	// 数据类型，填啥都行，你需要什么就填什么样的类型
	}

	public static class UnionFindSet {
	//（key，value）表示，key 的父节点，是 value，即左边的是子，右边的是父
	public HashMap<Data, Data> fatherMap;
	public HashMap<Data, Integer> sizeMap;

	public UnionFindSet(List<Data> nodes) {
	fatherMap = new HashMap<Data, Data>();
	sizeMap = new HashMap<Data, Integer>();
	makeSets(nodes);
	}

	// 想要使用并查集，必须先给我初始化并查集
	// 初始化的时候每一个节点都是父节点，自己指向自己，且 sizeMap 为 1
	private void makeSets(List<Data> nodes) {
	fatherMap.clear();
	sizeMap.clear();
	for (Data node : nodes) {
	fatherMap.put(node, node);
	sizeMap.put(node, 1);
	}
	}

	//find 的过程，递归实现，并把沿途的所有结点都指向父节点
	private Data find(Data node) {
	Data father = fatherMap.get(node);
	if (father != node) {
	father = find(father);
	}
	fatherMap.put(node, father);
	return father;
	}

	// 判断是否是同一个代表节点
	public boolean isSameSet(Data a, Data b) {
	return find(a) == find(b);
	}

	// 联合方法，把小节点接到大节点下面
	public void union(Data a, Data b) {
	if (a == null \|\| b == null) {
	return;
	}
	Data aHead = find(a);
	Data bHead = find(b);
	if (aHead != bHead) {
	Integer aSetSize = sizeMap.get(aHead);
	Integer bSetSize = sizeMap.get(bHead);
	if (aSetSize <= bSetSize) {
	fatherMap.put(aHead, bHead);
	sizeMap.put(bHead, aSetSize + bSetSize);
	} else {
	fatherMap.put(bHead, aHead);
	sizeMap.put(aHead, aSetSize + bSetSize);
	}
	}
	}
	}
	}

# 复杂度分析

令 n 为图中点的个数。

首先分析空间复杂度。空间上，由于我们需要存储 parent （带权并查集还有 weight），因此空间复杂度取决于于图中的点的个数，空间复杂度不难得出为 $O(n)$ 。
并查集的时间消耗主要是 union 和 find 操作，路径压缩和按秩合并优化后的时间复杂度接近于 O (1)。更加严谨的表达是 O (log (m×Alpha (n)))，n 为合并的次数， m 为查找的次数，这里 Alpha 是 Ackerman 函数的某个反函数。但如果只有路径压缩或者只有按秩合并，两者时间复杂度为 O (logx) 和 O (logy)，x 和 y 分别为合并与查找的次数。