1

这个星期天我要考试，我只是想确认我所做的是否正确（你知道考试让我怀疑）

这是算法的工作原理：

int Find(int x)
{ // Return the set containing x and compress the path from x to root
  // First, find the root
int z = x; while (P[z] > 0) { z = P[z]; } int root = z;
// Start at x again and reset the parent // of every node on the path from x to root z = x;
while (P[z] > 0)
{ int t = P[z];
     P[z] = root; // Reset Parent of z to root
z = t; }
return root; }

这是问题：

回想一下为一组 n 个元素的不相交集上的 Union-Find 问题开发的算法。Find 使用路径压缩，Union 使用排名。此外，相同等级的两棵树的联合选择与第二个参数关联的根作为新根。从集合 S = {1, 2, ..., 10} 和 10 个不相交的子集开始，每个子集包含一个元素。一个。执行后绘制最后一组树：
Union(1,2)、Union(3,4)、Union(5,6)、Union(1,5)、Union(1,3)。

这是我对这个问题的解决方案：

在此处输入图像描述

我很想有关于这个算法的任何提示或建议。

谢谢！

4

1 回答 1

0

Find操作的关键Union-Find Set是路径压缩。

如果我们知道集合 Ar1的根是 ，集合 B 的根是r2，那么当将集合 A 和集合 B 连接在一起时。最简单的方法是将集合 B 的根设为集合 A 的根，即father[r2] = r1;

但它就不是那么“聪明”了r2，我们说，当我们的儿子x想知道它的根时，x问它的父亲r2，然后父亲r2问自己的父亲r1，blabla，直到找到根r1。下次再问x's root 时，x问它的父亲r1“我们的 root 是什么？ ”，就没有必要r1再重复前面的循环了。既然r1已经知道它的根是什么r2，r1就可以直接将其归还x。

简而言之，x's root'也是x'父亲'的根源。所以我们得到了如何实现路径压缩（我认为递归更直接）：

int Find(int x)
{
    // initial each element's root as itself, which means father[x] = x;
    // if an element finds its father is itself, means root is found
    if(x == father[x])
        return father[x];
    int temp = father[x];
    // root of x's father is same with root of x's father's root
    father[x] = Find(temp);
    return father[x];
}

它具有极高的性能，关于路径压缩查找操作的时间复杂度，请参见：http ://www.gabrielnivasch.org/fun/inverse-ackermann

于 2015-02-09T13:32:54.870 回答