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