联盟查找数据结构

Question

对于许多问题,我看到推荐的解决方案是使用union-find数据结构.我试着阅读它并思考它是如何实现的(使用C++).我目前的理解是它只是一组集合.因此,要找到元素所属的集合,我们需要n*log n操作.当我们必须执行union时,我们必须找到需要合并的两个集合set_union并对它们进行处理.这对我来说看起来并不十分有效.我对这个数据结构的理解是正确的还是我错过了什么？

Answer 1

这是很晚的回复,但这可能在stackoverflow上没有得到解答,因为这是搜索union-find的人的最顶层页面,这里是详细的解决方案.

Find-Union是一种非常快速的操作,在接近恒定的时间内执行.它遵循Jeremie对路径压缩和跟踪集合大小的见解.对每个查找操作本身执行路径压缩,从而采用摊销的lg*(n)时间.lg*就像逆Ackerman函数,增长非常慢,很少超过5(至少直到n <2 ^ 65535).Union/Merge集合是懒惰的,只需将1个根指向另一个,特别是较小的set的根到较大的set的根,这是在恒定时间内完成的.

请参阅以下代码:https://github.com/kartikkukreja/blog-codes/blob/master/src/Union%20Find%20%28Disjoint%20Set%29%20Data%20Structure.cpp

class UF {
  int *id, cnt, *sz;
  public:
// Create an empty union find data structure with N isolated sets.
UF(int N) {
    cnt = N; id = new int[N]; sz = new int[N];
    for (int i = 0; i<N; i++)  id[i] = i, sz[i] = 1; }
~UF() { delete[] id; delete[] sz; }

// Return the id of component corresponding to object p.
int find(int p) {
    int root = p;
    while (root != id[root])    root = id[root];
    while (p != root) { int newp = id[p]; id[p] = root; p = newp; }
    return root;
}
// Replace sets containing x and y with their union.
void merge(int x, int y) {
    int i = find(x); int j = find(y); if (i == j) return;
    // make smaller root point to larger one
    if (sz[i] < sz[j]) { id[i] = j, sz[j] += sz[i]; }
    else { id[j] = i, sz[i] += sz[j]; }
    cnt--;
}
// Are objects x and y in the same set?
bool connected(int x, int y) { return find(x) == find(y); }
// Return the number of disjoint sets.
int count() { return cnt; }
};

Answer 2

数据结构可以表示为树,其中分支反转(而不是向下指向,分支向上指向父级 - 并将子级与其父级链接).

如果我没记错的话,可以很容易地显示出来:

• 那个路径压缩(每当你查找集合A的"父"时,你"压缩"路径,以便将来每次调用这些将为父节点提供时间O(1))将导致O(log n )每次通话的复杂性;

• 平衡(你大致跟踪每个集合中的孩子数量,当你必须"联合"两个集合时,你创建一个孩子少的孩子的那个)也导致一个O(日志) n)每次通话的复杂性.

更复杂的证明可以表明,当你结合两种优化时,你得到的平均复杂度是反Ackermann函数,写成α(n),这是Tarjan对这种结构的主要发明.

我相信,后来证明,对于某些特定的使用模式,这种复杂性实际上是不变的(尽管对于所有实际目的,ackermann的逆约为4).根据Union-Find的维基百科页面,在1989年,任何等效数据结构的每次操作的摊余成本显示为Ω(α(n)),证明当前的实现是渐近最优的.

Answer 3

正确的联合查找数据结构在每次查找期间都使用路径压缩。这会摊销成本，然后每个操作与阿克曼函数的倒数成正比，这基本上使其恒定（但不完全）。

如果您从头开始实现它，那么我建议使用基于树的方法。