网站建设资金管理办法,下载微信app软件,镜像的网站怎么做排名,一度设计公司什么是不相交集数据结构#xff1f; 如果两个集合没有任何共同元素#xff0c;则它们被称为不相交集#xff0c;集合的交集为空集。 存储不重叠或不相交元素子集的数据结构称为不相交集合数据结构。不相交集合数据结构支持以下操作#xff1a;
1、将新集合添加到不相交集合…
什么是不相交集数据结构 如果两个集合没有任何共同元素则它们被称为不相交集集合的交集为空集。 存储不重叠或不相交元素子集的数据结构称为不相交集合数据结构。不相交集合数据结构支持以下操作
1、将新集合添加到不相交集合中。
2、使用联合操作将不相交集合并为单个不相交集。
3、使用“查找”操作查找不相交集的代表。
4、检查两个集合是否不相交。
考虑这样一个情况有许多人需要执行以下任务 1、添加新的友谊关系即一个人 x 成为另一个人 y 的朋友即向集合中添加新元素。 2、判断个体x 是否是个体 y 的朋友直接或间接朋友
例子 我们有 10 个人比如 a、b、c、d、e、f、g、h、i、j 以下是需要添加的关系 a - b b - d c - f c - i j - e g - j 给定查询例如 a 是否是 d 的朋友。我们基本上需要创建以下 4 个组并在组项之间保持快速访问的连接 G1 {a, b, d} G2 {c, f, i} G3 {e, g, j} G4 {h}
判断 x 和 y 是否属于同一组即判断 x 和 y 是否是直接/间接朋友。 根据个体所属的组别将个体划分为不同的集合。此方法称为不相交集合并集它维护不相交集合的集合每个集合由其成员之一表示。
要回答上述问题需要考虑两个关键点 1、如何解析集合最初所有元素都属于不同的集合。在处理给定的关系后我们选择一个成员作为代表。选择代表的方法有很多种一种简单的方法是选择最大的索引。 2、检查两个人是否在同一组中如果两个人的代表相同那么他们就会成为朋友。
使用的数据结构包括 数组整数数组称为Parent[]。如果我们处理N 个项目则数组的第 i 个元素代表第 i 个项目。更准确地说Parent[] 数组的第 i 个元素是第 i 个项目的父级。这些关系创建一个或多个虚拟树。 树它是一个不相交集。如果两个元素在同一棵树中那么它们就在同一个不相交集。每棵树的根节点或最顶端节点称为集合的代表。每个集合始终有一个唯一的代表。识别代表的一个简单规则是如果“i”是集合的代表则Parent[i] i。如果 i 不是其集合的代表则可以通过沿树向上移动直到找到代表来找到它。
不相交集合数据结构上的操作 查找 联合
1. 查找 可以通过递归遍历父数组直到找到其自身的父节点来实现。
# Finds the representative of the set # that i is an element of def find(i): # If i is the parent of itself if (parent[i] i): # Then i is the representative of # this set return i else: # Else if i is not the parent of # itself, then i is not the # representative of his set. So we # recursively call Find on its parent return find(parent[i]) # The code is contributed by Nidhi goel
时间复杂度这种方法效率低下在最坏的情况下可能需要 O(n) 时间。
2. 联合 它以两个元素作为输入并使用查找操作找到它们的集合的代表最后将其中一棵树代表集合放在另一棵树的根节点下。
# Unites the set that includes i # and the set that includes j def union(parent, rank, i, j): # Find the representatives # (or the root nodes) for the set # that includes i irep find(parent, i) # And do the same for the set # that includes j jrep find(parent, j) # Make the parent of i’s representative # be j’s representative effectively # moving all of i’s set into j’s set) parent[irep] jrep
时间复杂度这种方法效率低下在最坏的情况下可能导致长度为 On的树。
优化按等级/大小合并和路径压缩 效率在很大程度上取决于哪棵树连接到另一棵树。有两种方法可以实现。第一种是按等级联合它将树的高度视为一个因素第二种是按大小联合它将树的大小视为一个因素同时将一棵树连接到另一棵树。此方法与路径压缩一起提供了几乎恒定时间的复杂性。
路径压缩对 Find() 的修改 它通过压缩树的高度来加速数据结构。这可以通过在Find操作中插入一个小的缓存机制来实现。查看代码了解更多详细信息
# Finds the representative of the set that i # is an element of. def find(i): # If i is the parent of itself if Parent[i] i: # Then i is the representative return i else: # Recursively find the representative. result find(Parent[i]) # We cache the result by moving i’s node # directly under the representative of this # set Parent[i] result # And then we return the result return result # The code is contributed by Arushi Jindal.
时间复杂度平均每次调用为 O(log n)。
按等级合并 首先我们需要一个新的整数数组名为rank[] 。此数组的大小与父数组Parent[]相同。如果 i 代表一个集合则rank[i]就是代表该集合的树的高度。 现在回想一下在 Union 操作中将两棵树中的哪一棵移动到另一棵之下并不重要。现在我们要做的是最小化结果树的高度。如果我们要合并两棵树或集合我们将它们称为左和右那么这一切都取决于左的等级和右的等级。 1、如果左边的等级小于右边的等级那么最好将左边移到右边的下方因为这不会改变右边的等级而将右边移到左边的下方会增加高度。同样如果右边的等级小于左边的等级那么我们应该将右边移到左边的下方。 2、如果等级相等那么哪棵树位于另一棵树之下并不重要但结果的等级始终比树的等级大一。
class DisjointSet: def __init__(self, size): self.parent [i for i in range(size)] self.rank [0] * size # Function to find the representative (or the root node) of a set def find(self, i): # If i is not the representative of its set, recursively find the representative if self.parent[i] ! i: self.parent[i] self.find(self.parent[i]) # Path compression return self.parent[i] # Unites the set that includes i and the set that includes j by rank def union_by_rank(self, i, j): # Find the representatives (or the root nodes) for the set that includes i and j irep self.find(i) jrep self.find(j) # Elements are in the same set, no need to unite anything if irep jrep: return # Get the rank of is tree irank self.rank[irep] # Get the rank of js tree jrank self.rank[jrep] # If is rank is less than js rank if irank jrank: # Move i under j self.parent[irep] jrep # Else if js rank is less than is rank elif jrank irank: # Move j under i self.parent[jrep] irep # Else if their ranks are the same else: # Move i under j (doesnt matter which one goes where) self.parent[irep] jrep # Increment the result trees rank by 1 self.rank[jrep] 1 def main(self): # Example usage size 5 ds DisjointSet(size) # Perform some union operations ds.union_by_rank(0, 1) ds.union_by_rank(2, 3) ds.union_by_rank(1, 3) # Find the representative of each element for i in range(size): print(fElement {i} belongs to the set with representative {ds.find(i)}) # Creating an instance and calling the main method ds DisjointSet(size5) ds.main()
按大小合并 同样我们需要一个新的整数数组名为size[] 。此数组的大小与父数组Parent[]相同。如果 i 代表一个集合则size[i]是代表该集合的树中元素的数量。 现在我们将两棵树或集合合并起来我们将它们称为左树和右树在这种情况下一切都取决于左树或集合的大小和右树或集合的大小。 1、如果左边的尺寸小于右边的尺寸那么最好将左边移到右边下方并将右边的尺寸增加左边的尺寸。同样如果右边的尺寸小于左边的尺寸那么我们应该将右边移到左边下方并将左边的尺寸增加右边的尺寸。 2、如果尺寸相等那么哪棵树位于另一棵树下都没有关系。
# Python program for the above approach class UnionFind: def __init__(self, n): # Initialize Parent array self.Parent list(range(n)) # Initialize Size array with 1s self.Size [1] * n # Function to find the representative (or the root node) for the set that includes i def find(self, i): if self.Parent[i] ! i: # Path compression: Make the parent of i the root of the set self.Parent[i] self.find(self.Parent[i]) return self.Parent[i] # Unites the set that includes i and the set that includes j by size def unionBySize(self, i, j): # Find the representatives (or the root nodes) for the set that includes i irep self.find(i) # And do the same for the set that includes j jrep self.find(j) # Elements are in the same set, no need to unite anything. if irep jrep: return # Get the size of i’s tree isize self.Size[irep] # Get the size of j’s tree jsize self.Size[jrep] # If i’s size is less than j’s size if isize jsize: # Then move i under j self.Parent[irep] jrep # Increment js size by is size self.Size[jrep] self.Size[irep] # Else if j’s size is less than i’s size else: # Then move j under i self.Parent[jrep] irep # Increment is size by js size self.Size[irep] self.Size[jrep] # Example usage n 5 unionFind UnionFind(n) # Perform union operations unionFind.unionBySize(0, 1) unionFind.unionBySize(2, 3) unionFind.unionBySize(0, 4) # Print the representative of each element after unions for i in range(n): print(Element {}: Representative {}.format(i, unionFind.find(i))) # This code is contributed by Susobhan Akhuli
输出 元素 0代表 0 元素 1代表 0 元素 2代表 2 元素 3代表 2 元素 4代表 0
时间复杂度Olog n无路径压缩。
下面是具有路径压缩和按等级合并的不相交集的完整实现。
# Python3 program to implement Disjoint Set Data # Structure. class DisjSet: def __init__(self, n): # Constructor to create and # initialize sets of n items self.rank [1] * n self.parent [i for i in range(n)] # Finds set of given item x def find(self, x): # Finds the representative of the set # that x is an element of if (self.parent[x] ! x): # if x is not the parent of itself # Then x is not the representative of # its set, self.parent[x] self.find(self.parent[x]) # so we recursively call Find on its parent # and move is node directly under the # representative of this set return self.parent[x] # Do union of two sets represented # by x and y. def Union(self, x, y): # Find current sets of x and y xset self.find(x) yset self.find(y) # If they are already in same set if xset yset: return # Put smaller ranked item under # bigger ranked item if ranks are # different if self.rank[xset] self.rank[yset]: self.parent[xset] yset elif self.rank[xset] self.rank[yset]: self.parent[yset] xset # If ranks are same, then move y under # x (doesnt matter which one goes where) # and increment rank of xs tree else: self.parent[yset] xset self.rank[xset] self.rank[xset] 1 # Driver code obj DisjSet(5) obj.Union(0, 2) obj.Union(4, 2) obj.Union(3, 1) if obj.find(4) obj.find(0): print(Yes) else: print(No) if obj.find(1) obj.find(0): print(Yes) else: print(No) # This code is contributed by ng24_7. 输出
Yes No
时间复杂度创建 n 个单项集的时间为 O(n)。两种技术路径压缩和按等级/大小合并的时间复杂度将达到接近常数时间。事实证明最终的 摊销时间复杂度为 O(α(n))其中 α(n) 是逆阿克曼函数其增长非常稳定当 n10 600 时它甚至不会超过。
空间复杂度 On因为我们需要在不相交集数据结构中存储 n 个元素。
