并查集及其应用.pptVIP

并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 并查集及其应用 A．按秩合并 可以联系一下链表的优化，我们是选择比较小的一个集合归并到大的集合里去。对于有根树的结构，很类似地，也可以记录树上的节点数，将较小的树的根指向较大的树。但是有根树的结构又有非常特殊的地方，它的一个节点下面可能挂有很多子树；从前面分析也可以看出，主要的时间花在了FIND-SET（x）上，只要使得树中不存在一条偏长的路径，即使得各条路径的长度都比较平均了，那么算法就不会出现特别退化的情况。对每个结点，用一个秩（rank）来近似子树大小对数，同时它也是该节点高度的一个上界。进行UNION的时候，只要让具有较小秩的根指向具有较大秩的根。如果两根的秩相等，只要使其中一个根指向另一个，同时秩应当增加1。这十分类似于统计节点个数，但这里统计的是树的深度。 B．路径压缩优化方法 在分离集合森林中，分离集合是用分离集合树来表示的。分离集合树是用来联系集合中的元素的，只要同一集合中的元素在同一棵树上，不管它们在树中是如何被联系的，都满足分离集合树的要求。如下图，这两棵分离集合树是等价的，因为它们所包含的元素相同。显然，右边那棵树比较“优秀”，因为它具有比较低的深度，相应的，查找与合并的时间复杂度也较低。那么，我们就应该使分离集合树尽量向右树的形式靠拢。 在查找一个结点所在树的根结点的过程中，要经过一条从待查结点到根结点的路径。我们不妨就让这些路径上的结点直接指向根结点，作为根结点的子结点。这样，这些路径上的结点仍在分离集合中，整棵树仍然满足分离集合树的要求，而路径上的结点的深度无疑降低了，这些点及其子树上的结点的查找复杂度大大降低。如下图，描述了在一棵分离集合树查找结点7的前后所呈现出的结构。 这种改变结点所指方向以降低结点深度，从而缩短查找路径长度的方法，叫做路径压缩。实现路径压缩的最简单的方法是在查找从待查结点到根结点的路径时走两遍，第一遍找到树的根结点，第二遍改变路径上结点指向根结点（使它们的父结点为根结点）。 使用路径压缩大大提高了查找算法的效率。如果将带路径压缩的查找算法与优化过的合并算法联合使用，则可以证明，n次查找最多需要用O(n·α(n))时间。α(n)是单变量阿克曼函数的逆函数，它是一个增长速度比logn慢的多但又不是常数的函数，在一般情况下α(n)≤4，可以当作常数看。 这种方法是在FIND-SET(x)过程中作一些改进。设想，从x到它的根，我们必须经过一条路径，显然这条路径上的所有的根与x的根是同一个根，那么不妨在得到结果的同时，顺便把这条路上全部节点的根都改成x的根，也就是说，对这些节点进行了分散，其结果是，下一次如果再有这条路上的点进行FIND-SET(x)时，只要经过一步就可以找到根。可以认为是x顺便帮了帮大家的忙，把好处带给了大家，因此其它节点以后都省事了。 FIND-SET(x) 使用这两种方法优化后的代码： MAKE-SET(x) { p[x]:=x；rank[x]:=0；} UNION(x,y) { x:= FIND-SET(x)；y:= FIND-SET(Y)； if rank[x] rank[y] then p[y]:= x else { p[x]:= y if rank[x] = rank[y] then rank[y] := rank[y]+1; } } FIND-SET(x) { if xp[x]