并查集
维基百科,自由的 encyclopedia
在计算机科学中,并查集(英文:Disjoint-set data structure,直译为不交集数据结构)是一种数据结构,用于处理一些不交集(Disjoint sets,一系列没有重复元素的集合)的合并及查询问题。并查集支持如下操作:
- 查询:查询某个元素属于哪个集合,通常是返回集合内的一个“代表元素”。这个操作是为了判断两个元素是否在同一个集合之中。
- 合并:将两个集合合并为一个。
- 添加:添加一个新集合,其中有一个新元素。添加操作不如查询和合并操作重要,常常被忽略。
由于支持查询和合并这两种操作,并查集在英文中也被称为联合-查找数据结构(Union-find data structure)或者合并-查找集合(Merge-find set)。
“并查集”可以用来指代任何支持上述操作的数据结构,但是一般来说,“并查集”特指其中最常见的一种实现:不交集森林(Disjoint-set forest)。经过优化的不交集森林有线性的空间复杂度(,为元素数目,下同),以及接近常数的单次操作平均时间复杂度(,为反阿克曼函数),是效率最高的常见数据结构之一。
并查集是用于计算最小生成树的克鲁斯克尔算法中的关键。由于最小生成树在网络路由等场景下十分重要,并查集也得到了广泛的引用。此外,并查集在符号计算,寄存器分配等方面也有应用。