并查集

在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）定义了两个用于此数据结构的操作：

由于支持这两种操作，一个不相交集也常被称为联合-查找数据结构（union-find data structure）或合并-查找集合（merge-find set）。其他的重要方法，MakeSet，用于创建单元素集合。有了这些方法，许多经典的划分问题可以被解决。

为了更加精确的定义这些方法，需要定义如何表示集合。一种常用的策略是为每个集合选定一个固定的元素，称为代表，以表示整个集合。接着，Find(x) 返回x所属集合的代表，而Union使用两个集合的代表作为参数。

并查集森林是一种将每一个集合以树表示的数据结构，其中每一个节点保存着到它的父节点的引用（见意大利面条堆栈）。这个数据结构最早由Bernard A. Galler和Michael J. Fischer于1964年提出，但是经过了数年才完成了精确的分析。

在并查集森林中，每个集合的代表即是集合的根节点。“查找”根据其父节点的引用向根行进直到到底树根。“联合”将两棵树合并到一起，这通过将一棵树的根连接到另一棵树的根。实现这样操作的一种方法是

 function (x)     x.parent := x

 function (x)     if x.parent == x        return x     else        return (x.parent)

 function (x, y)     xRoot := (x)     yRoot := (y)     xRoot.parent := yRoot

这是并查集森林的最基础的表示方法，这个方法不会比链表法好，这是因为创建的树可能会严重不平衡；然而，可以用两种办法优化。

第一种方法，称为“按秩合并”，即总是将更小的树连接至更大的树上。因为影响运行时间的是树的深度，更小的树添加到更深的树的根上将不会增加秩除非它们的秩相同。在这个算法中，术语“秩”替代了“深度”，因为同时应用了路径压缩时（见下文）秩将不会与高度相同。单元素的树的秩定义为${\displaystyle 0}$(x) x.parent := x x.rank := 0

 function (x, y)     xRoot := (x)     yRoot := (y)     if xRoot == yRoot         return     // x和y不在同一个集合，合并它们。     if xRoot.rank < yRoot.rank         xRoot.parent := yRoot     else if xRoot.rank > yRoot.rank         yRoot.parent := xRoot     else         yRoot.parent := xRoot         xRoot.rank := xRoot.rank + 1

第二个优化，称为“路径压缩”，是一种在执行“查找”时扁平化树结构的方法。关键在于在路径上的每个节点都可以直接连接到根上；他们都有同样的表示方法。为了达到这样的效果，Find递归地经过树，改变每一个节点的引用到根节点。得到的树将更加扁平，为以后直接或者间接引用节点的操作加速。这儿是Find：

 function (x)     if x.parent != x        x.parent := (x.parent)     return x.parent

这两种方法的优势互补，同时使用二者的程序每个操作的平均时间仅为${\displaystyle O(\mathrm{\alpha <!--\; \alpha \; -->}(n))}$，${\displaystyle \mathrm{\alpha <!--\; \alpha \; -->}(n)}$是${\displaystyle n=f(x)=A(x,x)}$的反函数，其中${\displaystyle A}$是急速增加的阿克曼函数。因为${\displaystyle \mathrm{\alpha <!--\; \alpha \; -->}(n)}$是其的反函数，故${\displaystyle \mathrm{\alpha <!--\; \alpha \; -->}(n)}$在${\displaystyle n}$十分巨大时还是小于5。因此，平均运行时间是一个极小的常数。

实际上，这是渐近最优算法：Fredman和Saks在1989年解释了${\displaystyle \mathrm{\Omega <!--\; \Omega \; -->}(\mathrm{\alpha <!--\; \alpha \; -->}(n))}$的平均时间内可以获得任何并查集。

需要注意的是，一开始我们假设元素都是分别属于一个独立的集合里的。

操作很简单：先设置一个数组(数组)Father，表示x的“父亲”的编号。那么，合并两个不相交集合的方法就是，找到其中一个集合最父亲的父亲（也就是最久远的祖先），将另外一个集合的最久远的祖先的父亲指向它。

Pascal代码：

procedure Union(x,y:integer);{其中GetFather是下面将讲到的操作} var fx,fy : integer;  begin     fx := getfather(x);     fy := getfather(y);     If fx<>fy then father := fy;{指向最祖先的祖先}  end;