在计算机科学中，并查集（英文：Disjoint-setdatastructure，直译为不交集数据结构）是一种数据结构，用于处理一些不交集（Disjointsets，一系列没有重复元素的集合）的合并及查询问题。并查集支持如下操作：
查询：查询某个元素属于哪个集合，通常是返回集合内的一个“代表元素”。这个操作是为了判断两个元素是否在同一个集合之中。合并：将两个集合合并为一个。添加：添加一个新集合，其中有一个新元素。添加操作不如查询和合并操作重要，常常被忽略。由于支持查询和合并这两种操作，并查集在英文中也被称为联合-查找数据结构（Union-finddatastructure）或者合并-查找集合（Merge-findset）。
并查集是用于计算最小生成树的迪杰斯特拉算法中的关键。由于最小生成树在网络路由等场景下十分重要，并查集也得到了广泛的引用。此外，并查集在符号计算，寄存器分配等方面也有应用。
引论设计一个算法大致分为六个步骤：
定义问题（definetheproblem)设计一个算法来解决问题（Findanalgorithmtosolveit）判断算法是否足够高效？（FastEnough?)如果不够高效，思考为什么，并进行优化。（Ifnot，figureoutwhy?）寻找一种方式来处理问题(Findawaytoaddresstheproblem)迭代设计，直到满足条件(Iterateuntilsatisfied.)我们从一个基本问题：网络连通性（Networkconnectivity）出发，该问题可以抽象为：
一组对象。UNION命令：连接两个对象。FIND查询：是否有路径将一个对象连接到另一个对象？并查集的对象可以是下面列出的任何类型：
网络中的计算机互联网上的web页面计算机芯片中的晶体管。变量名称别名。数码照片中的像素。复合系统中的金属点位。图1连通图
在编程的时候，为了方便起见，我们对这些对象从0到n-1进行编号，从而用一个整形数字表示对象。隐藏与Union-find不相关的细节；可以使用整数快速获取与对象相关的信息（数组的下标）；可以使用符号表对对象进行转化。
简化有助于我们理解连通性的本质。
如图1所示，假设我们有编号为[0,1,2,3,4,5,6,7,8,9]的10个对象，对象的不相交集合为:{{0},{1},{2,3,9},{5,6},{7},{4,8}}。
Find查询：2和9是否在一个集合当中呢？
答：{{0},{1},{2,3,9},{5,6},{7},{4,8}}。
Union命令：合并包含3和8的集合。
答：{{0},{1},{2,3,4,8,9},{5,6},{7}}。
连接组件(ConnectedComponent)：一组相互连接的顶点.
每一次Union命令会将组（连通分量）的数量减少1个。
如上图所示，初始时，每一个顶点为一个组，我们执行了7次Union操作后，变成了3个组。其中{29}不算做一次Union操作，是因为在Union之前，我们使用Find查找命令，会发现{29}此时已经位于同一个组{}当中。
以网络连通性问题为例，如下图所示，find(u,v)可以判断顶点u和v是否联通？
如下图所示，图中共包含63个组，其中对象u和对象v在同一个集合当中，我们可以找到一条从对象u到对象v的路径（红色路线）但是我们并不关心这条路劲本身，只关心他们是否联通：
上面的问题看似很复杂，但也很容易抽象为Union-Find模型：
对象。对象的不相交集（DisjointSet）。Find查询：两个对象是否在同一集合中？Union命令：将包含两个对象的集合替换为它们的并集。现在目标就是为Union-Find设计一个高效的数据结构：
Find查询和Union命令可以混合使用。Find和Union的操作数量M可能很大。对象数量N可能很大。Quick-Find设计一个大小为N的整型数组id[]，如果p和q有相同的id，即id[p]=id[q]，则认为p和q是联通的，位于同一个集合中，如下图所示，5和6是联通的，2、3、4和9是联通的。
Find(p,q)查询操作只需要判断p和q是否具有相同的id，即id[p]是否等于id[q]；比如查询Find(2,9)，id[2]=id[9]=9，则2和9是联通的。
Union(p,q)操作：合并包含p和q的所有组，将输入中所有id为id[p]的对象id修改为id[q]。比如Union(3,6)，需要将id为id[3]=9的所有对象{2,3,4,9}的id均修改为id[6]=6，如下图所示。
Find(u,v)的时间复杂度为
，Union(p,q)的时间复杂度为
量级，每一次Union操作需要更新很多元素i的indexid。
以下图为例，我们依次执行Union(3,4)，Union(4,9)，Union(8,0)，Union(2,3)，......，Union(6,1)操作，整形数组id[]中元素的变化过程。
实现publicclassQuickFind{privateint[]id;publicQuickFind(intN){id=newint[N];for(inti=0;iN;i++){id=i;}}publicbooleanfind(intp,intq){returnid[p]==id[q];}publicvoidunite(intp,intq){intpid=id[p];for(inti=0;iid.length;i++){if(id==pid){id=id[q];}}}}复杂度分析
Quick-find算法的find函数非常简单，只是判断id[p]==id[q]并返回，时间复杂度为
，而Union(u,v)函数因为无法确定谁的ID与id[q]相同，所以每次都要把整个数组遍历一遍，如果一共有
个对象，则时间复杂度为
。综合一下，表示如果Union操作执行
次，总共
个对象（数组大小），则时间复杂度为
量级，。
因为这个算法Find操作很快，而Union操作却很慢，所以将其称为Quick-Find算法。
Quick-Union回忆Quick-Find中union函数，就像是暴力法，遍历所有对象的id[]，然后把有着相同id的数全部改掉，Quick-Union算法则是引入“树”的概念来优化union函数，我们把每一个数的id看做是它的父结点。比如说，id[3]=4，就表示3的父结点为4。
与Quick-Find算法使用一样的数据结构，但是id[]数组具有不同的含义：
大小为的整型数组id[]解释：id表示i的父结点i的根结点为id[id[id[...id...]]]
如图所示，id[2]=9就表示2的父结点为9；3的根节点为9(3的父结点为4，4的父结点为9，9的父结点还是9，也就是根结点了)，5的根结点为6。
那么Find(p,q)操作就变成了判断p和q的根结点是否相同，比如Find(2,3)，2和3的根结点9相同，所以2和3是联通的。
Union(p,q)操作就是将q根结点的id设置为p的根结点的id。如上图所示，Union(3,5)就是将5的根结点的6设置为3的根结点9，即id[5]=9，仅更新一个元素的id。
对于原数组i={0,1,2,3,4,5,6,7,8,9}及id数组id[10]={0,1,2,3,4,5,6,7,8,9}，依次执行Union(3,4)，Union(4,9)，Union(8,0)，Union(2,3)，Union(5,6)，Union(5,9)，Union(7,3)，Union(4,8)，Union(6,2)的过程中如下：
实现代码publicclassQuickUnion{privateint[]id;publicQuickUnion(intN){id=newint[N];for(inti=0;iN;i++)id=i;}privateintroot(inti){while(i!=id)i=id;returni;}publicbooleanfind(intp,intq){returnroot(p)==root(q);}publicvoidunite(intp,intq){inti=root(p);intj=root(q);id=j;}}复杂度分析
对于Find(p,q)操作，只需要找到p的根结点和q的根结点，检查它们是否相等。合并操作就是找到两个根节点并将第一个根节点的id记录值设为第二个根节点。
与Quick-Find算法相比，Quick-Union算法对于问题规模较大时是更加高效。不幸的是，Quick-Union算法快了一些但是依然太慢了，相对Quick-Find的慢，它是另一种慢。有些情况下它可以很快，而有些情况下它还是太慢了。但Quick-Union算法依然是用来求解动态连通性问题的一个快速而优雅的设计。
Quick-Union算法的缺点在于树可能太高了。这意味着查找操作的代价太大了。你可能需要回溯一棵瘦长的树（斜树），每个对象只是指向下一个节点，那么对叶子节点执行一次查找操作，需要回溯整棵树，只进行查找操作就需要花费N次数组访问，如果操作次数很多的话这就太慢了。
Find操作：最好时间复杂度为
，最坏为
，平均
。
Union操作：最好时间复杂度为
，最坏为
，平均
当进行
次Union操作，那么平均时间复杂度就是
。
WeightedQuick-Union好，我们已经看了快速合并和快速查找算法，两种算法都很容易实现，但是不支持巨大的动态连通性问题。那么，我们该怎么改进呢？
一种非常有效的改进方法，叫做加权。也许我们在学习前面两个算法的时候你已经想到了。这个改进的想法是在实现Quick-Union算法的时候执行一些操作避免得到一颗很高的树。
如果一棵大树和一棵小树合并，避免将大树放在小树的下面，就可以一定程度上避免更高的树，这个加权操作实现起来也相对容易。我们可以跟踪每棵树中对象的个数，然后我们通过确保将小树的根节点作为大树的根节点的子节点以维持平衡，所以，我们避免将大树放在小树下面的情况。
如上图所示，以Union(5,3)为例，5的根结点为6，3的根结点为9：
Quick-Union：以9为根结点树将作为6的子树WeightedQuick-Union：以6为根结点的树将作为9的子树。我们可以看一下WeightedQuick-Union操作的例子：
可以看到WeightedQuick-Union所生成的树很“胖”，刚好满足我们的需求。
实现代码WeightedQuick-Union的实现基本和Quick-Union一样，我们只需要维护一个数组sz[]，用来保存以i为根的树中的对象个数，比如sz[0]=1，就表示以0为根的树包含1个对象。
publicclassWeightedQuickUnion{privateint[]id;privateint[]sz;publicWeightedQuickUnion(intN){id=newint[N];sz=newint[N];for(inti=0;iN;i++){id=i;sz=1;//初始时，每一个结点为一棵树，sz=1}}privateintroot(inti){while(i!=id)i=id;returni;}publicbooleanfind(intp,intq){returnroot(p)==root(q);}publicvoidunite(intp,intq){inti=root(p);intj=root(q);if(szsz[j]){id=j;sz[j]+=sz;}else{id[j]=i;sz+=sz[j];}}}复杂度分析
对于加权Quick-Union算法处理
个对象和
条连接时最多访问
次，其中
为常数，即时间复杂度为
量级。与Quick-Find算法（以及某些情况下的Quick-Union算法）的时间复杂度
形成鲜明对比。
Find操作：
Union操作：
Union-Find
Union-Find算法是在WeightedQuick-Union的基础之上进一步优化，即路径压缩的WeightedQuick-Union算法。WeightedQuick-Union算法通过对Union操作进行加权保证Quick-Union算法可能出现的“瘦高”情况发生。而Union-Find算法是通过路径压缩进一步将WeightedQuick-Union算法的树高降低。
所谓路径压缩，就是在计算结点i的根之后，将回溯路径上的每个被检查结点的id设置为**root(i)**。
如下图所示，root(9)=0，从结点9到根结点0的路径为9→6→3→1→0，则将6,3,1的根结点设置为0。这样一来，树的高度一下子就变矮了，而且对于Union和Find操作没有任何影响。
路径压缩：
标准实现：在root()中添加第二个循环，将每个被遍历到的结点的的id设置为根结点。privateintroot(inti){introot=i;//找到结点i的根结点rootwhile(root!=id[root])root=id[root];//每个被遍历到的结点的的id设置为根结点rootwhile(i!=root){inttmp=id;id=root;i=tmp;}returnroot;}简化的实现：使路径中的所有其他结点指向其祖父结点，即id=id[id]。
privateintroot(inti){while(i!=id){id=id[id];//简化的方法i=id;}returni;}
在实践中，我们没有理由不选择简化的方式，简化的方式同样可以使树几乎完全平坦，如下图所示：
复杂度分析定理：从一个空数据结构开始，对
个对象执行
次Union和Find操作的任何序列都需要
时间。时间复杂度的具体证明非常困难，但这并不妨碍算法的简单性！
路径压缩的加权Quick-Union（WeigthedQuick-UnionwithPathCompression）算法虽是最优算法，但是并非所有操作都能在常数时间内完成。也就是，WQUPC算法的每个操作在最坏情况下（即均摊后）都不是常数级别的，而且不存在其他算法能够保证Union-Find算法的所有操作在均摊后都是常数级别。
各类算法时间复杂度对比算法UnionFind最坏时间复杂度Quick-FindN1MNQuick-UniontreeHeighttreeHeightMNWeightedQuick-UnionlgNlgNN+MlogNWQUPCVerynearto1(amortized)Verynearto1(amortized)(N+M)logN对于大规模的数据，比如包含
个顶点，
条边的图，WQUPC可以将时间从年降低到1分钟之内就可以处理完，而这是超级计算机也无法匹敌的。对于同一问题，使用一部手机运行的WQUPC轻松击败在超级计算机上运行的Quick-Find算法，这也许就是算法的魅力。
并查集的应用网络连通性问题渗滤图像处理。最近公共祖先。有限状态自动机的等价性。Hinley-Milner的多态类型推断。Kruskal的最小生成树算法。游戏(围棋、十六进制)。在Fortran中的编译语句的等价性问题预览时标签不可点收录于话题#个上一篇下一篇