algorithm - Union-Find Disjoint+路径压缩算法

Question

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

算法是这样工作的:

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; }

问题是:

Recall the algorithms developed for the Union-Find problem on disjoint sets from a set of n elements. Find uses path compression and Union uses ranking. Also, Union of two trees of the same rank chooses the root associated with 2nd argument as the new root. Start with a set S = {1, 2, ..., 10} and 10 disjoint subsets, each containing a single element. a. Draw the final set of trees after executing:
Union(1,2), Union(3,4), Union(5,6), Union(1,5), Union(1,3).

这是我对这个问题的解答:

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

谢谢!

Answer 1

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

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

但它并不是那么“聪明”，当 r2 的儿子，我们说 x，想知道它的根 x问它的父亲r2，然后父亲r2问自己的父亲r1，blabla，直到根r1 .下次当再次询问 x 的根时，x 会询问其父亲 r1 “我们的根是什么？”， r1 没有必要再次重复之前的循环。由于r1已经知道它的根是r2，r1可以直接将它返回给x。

简而言之，x 的根也是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