数据结构之并查集（Union-Find）

并查集Union-Find详解1. 引言并查集Union-Find是一种高效的数据结构主要用于解决动态连通性问题。它能够快速地判断两个元素是否属于同一个集合以及将两个不同的集合合并成一个集合。并查集在图论、网络连接、最小生成树算法如Kruskal算法等领域有广泛应用。2. 基本概念2.1 定义并查集维护一个集合的划分支持两种基本操作Find(x)查找元素x所在的集合或称为查找x的根节点Union(x, y)将包含x和y的两个集合合并2.2 核心思想并查集通过树形结构来表示集合每个集合由一棵树表示树中的每个节点指向其父节点。根节点是集合的代表元素用于标识整个集合。3. 基础实现3.1 数组实现最简单的实现方式是使用数组来存储父节点信息classUnionFind:def__init__(self,n):self.parentlist(range(n))# 初始化每个元素的父节点为自己deffind(self,x):# 基础查找递归查找根节点ifself.parent[x]!x:returnself.find(self.parent[x])returnxdefunion(self,x,y):# 基础合并将y的根节点指向x的根节点root_xself.find(x)root_yself.find(y)ifroot_x!root_y:self.parent[root_y]root_x3.2 时间复杂度分析基础实现的并查集在最坏情况下时间复杂度为O(n)因为可能需要遍历整个树来找到根节点。4. 优化技术4.1 路径压缩Path Compression路径压缩是在查找过程中将路径上的所有节点直接指向根节点从而减少后续查找的时间deffind(self,x):ifself.parent[x]!x:self.parent[x]self.find(self.parent[x])# 递归查找并压缩路径returnself.parent[x]4.2 按秩合并Union by Rank按秩合并是在合并时将较矮的树合并到较高的树下保持树的高度较小def__init__(self,n):self.parentlist(range(n))self.rank[0]*n# 记录每个树的高度defunion(self,x,y):root_xself.find(x)root_yself.find(y)ifroot_xroot_y:return# 按秩合并将秩较小的树合并到秩较大的树下ifself.rank[root_x]self.rank[root_y]:self.parent[root_x]root_yelifself.rank[root_x]self.rank[root_y]:self.parent[root_y]root_xelse:self.parent[root_y]root_x self.rank[root_x]14.3 按大小合并Union by Size另一种优化方式是按集合大小合并将较小的集合合并到较大的集合下def__init__(self,n):self.parentlist(range(n))self.size[1]*n# 记录每个集合的大小defunion(self,x,y):root_xself.find(x)root_yself.find(y)ifroot_xroot_y:return# 按大小合并将较小的集合合并到较大的集合下ifself.size[root_x]self.size[root_y]:self.parent[root_x]root_y self.size[root_y]self.size[root_x]else:self.parent[root_y]root_x self.size[root_x]self.size[root_y]5. 完整优化实现结合路径压缩和按秩合并的并查集实现classUnionFind:def__init__(self,n):self.parentlist(range(n))self.rank[0]*ndeffind(self,x):ifself.parent[x]!x:self.parent[x]self.find(self.parent[x])# 路径压缩returnself.parent[x]defunion(self,x,y):root_xself.find(x)root_yself.find(y)ifroot_xroot_y:returnFalse# 已经在同一集合中# 按秩合并ifself.rank[root_x]self.rank[root_y]:self.parent[root_x]root_yelifself.rank[root_x]self.rank[root_y]:self.parent[root_y]root_xelse:self.parent[root_y]root_x self.rank[root_x]1returnTruedefconnected(self,x,y):returnself.find(x)self.find(y)6. 时间复杂度分析经过优化的并查集具有接近常数时间的操作Find操作O(α(n))其中α是反阿克曼函数增长极其缓慢Union操作O(α(n))Connected操作O(α(n))对于实际应用中的n值α(n)通常小于5因此可以认为这些操作的时间复杂度接近O(1)。7. 应用场景7.1 图的连通性判断判断无向图中两个节点是否连通defis_connected(graph,n):ufUnionFind(n)foru,vingraph.edges:uf.union(u,v)returnuf.connected(start_node,end_node)7.2 最小生成树Kruskal算法Kruskal算法使用并查集来检测添加边时是否形成环defkruskal_mst(edges,n):ufUnionFind(n)mst[]edges.sort(keylambdax:x[2])# 按权重排序foru,v,weightinedges:ifuf.union(u,v):mst.append((u,v,weight))returnmst7.3 网络连接问题模拟网络中节点的连接和断开classNetwork:def__init__(self,n):self.ufUnionFind(n)defconnect(self,a,b):self.uf.union(a,b)defquery(self,a,b):returnself.uf.connected(a,b)7.4 等价类问题处理等价关系将具有相同性质的元素分组deffind_equivalence_classes(elements,relations):ufUnionFind(len(elements))fora,binrelations:uf.union(a,b)# 获取每个元素的根节点作为等价类的标识classes{}foriinrange(len(elements)):rootuf.find(i)ifrootnotinclasses:classes[root][]classes[root].append(elements[i])returnlist(classes.values())8. 扩展功能8.1 路径统计扩展并查集以支持路径统计classUnionFindWithPathCount:def__init__(self,n):self.parentlist(range(n))self.rank[0]*n self.path_count[1]*n# 每个集合的节点数deffind(self,x):ifself.parent[x]!x:self.parent[x]self.find(self.parent[x])returnself.parent[x]defunion(self,x,y):root_xself.find(x)root_yself.find(y)ifroot_xroot_y:returnFalseifself.rank[root_x]self.rank[root_y]:self.parent[root_x]root_y self.path_count[root_y]self.path_count[root_x]elifself.rank[root_x]self.rank[root_y]:self.parent[root_y]root_x self.path_count[root_x]self.path_count[root_y]else:self.parent[root_y]root_x self.rank[root_x]1self.path_count[root_x]self.path_count[root_y]returnTruedefget_size(self,x):returnself.path_count[self.find(x)]8.2 动态连通性支持动态添加节点和边的并查集classDynamicUnionFind:def__init__(self):self.parent{}self.rank{}defadd(self,x):ifxnotinself.parent:self.parent[x]x self.rank[x]0deffind(self,x):ifself.parent[x]!x:self.parent[x]self.find(self.parent[x])returnself.parent[x]defunion(self,x,y):self.add(x)self.add(y)root_xself.find(x)root_yself.find(y)ifroot_xroot_y:returnFalseifself.rank[root_x]self.rank[root_y]:self.parent[root_x]root_yelifself.rank[root_x]self.rank[root_y]:self.parent[root_y]root_xelse:self.parent[root_y]root_x self.rank[root_x]1returnTrue9. 性能对比实现方式Find时间Union时间空间复杂度基础实现O(n)O(n)O(n)路径压缩O(α(n))O(α(n))O(n)按秩合并O(α(n))O(α(n))O(n)完整优化O(α(n))O(α(n))O(n)10. 优缺点分析10.1 优点高效性经过优化的并查集操作接近常数时间简单性实现相对简单易于理解和维护灵活性可以轻松扩展以支持更多功能空间效率只需要O(n)的额外空间10.2 缺点不支持分割操作无法将一个集合分割成两个集合路径压缩可能增加递归深度在极端情况下可能导致栈溢出不适用于需要快速查找所有元素的操作需要遍历整个集合11. 实际应用案例11.1 社交网络分析classSocialNetwork:def__init__(self,n):self.ufUnionFind(n)defadd_friendship(self,a,b):self.uf.union(a,b)defare_friends(self,a,b):returnself.uf.connected(a,b)defget_connected_components(self):components{}foriinrange(self.uf.parent):rootself.uf.find(i)ifrootnotincomponents:components[root][]components[root].append(i)returnlist(components.values())11.2 图的连通分量统计defcount_connected_components(graph,n):ufUnionFind(n)foru,vingraph.edges:uf.union(u,v)# 统计不同的根节点数量rootsset()foriinrange(n):roots.add(uf.find(i))returnlen(roots)12. 总结并查集是一种非常实用的数据结构特别适合处理动态连通性问题。通过路径压缩和按秩合并等优化技术它能够在几乎常数时间内完成查找和合并操作。在实际应用中并查集被广泛应用于图算法、网络分析、等价类划分等领域。选择并查集时需要考虑问题是否涉及动态连通性是否需要高效的查找和合并操作是否可以接受不支持分割操作的限制