对于许多问题,我看到推荐的解决方案是使用联合查找数据结构。我试图阅读它,并思考如何实现(使用C++)。我目前的理解是,它不过是一组列表。因此,要查找元素属于哪个集合,我们需要n*log n
操作。当我们必须执行联合时,我们必须找到两个需要合并的集合,并对它们进行set_union
编码。对我来说,这看起来效率不高。我对这种数据结构的理解是正确的还是缺少什么?
最佳答案
这是一个很晚的答复,但是在stackoverflow上的其他地方可能没有得到答复,并且由于这是搜索union-find的用户的最高页面,所以这里是详细的解决方案。
Find-Union是一项非常快的操作,几乎在恒定时间内执行。
它遵循了Jeremie对路径压缩和跟踪集大小的见解。对每个查找操作本身执行路径压缩,从而花费lg *(n)的时间。 lg *类似于反阿克曼函数,增长非常缓慢,以至于很少超过5(至少直到n
请引用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; }
};
关于c++ - union 查找数据结构,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/8300125/