c – 联合查找数据结构

前端之家收集整理的这篇文章主要介绍了c – 联合查找数据结构前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
对于许多问题,我看到的解决方案是使用union-find数据结构.我试图阅读它,并考虑如何实现(使用C).我目前的理解是,它只不过是一套.所以要找到属于哪一个元素,我们需要n * log n操作.当我们要执行工会时,我们必须找到需要合并的两个集合,并对它们执行一个set_union.这对我来说看起来并不高效.我对这个数据结构的理解是正确的还是我错过了什么?

解决方法

这是相当晚的回复,但这可能没有在stackoverflow的其他地方回答,因为这是搜索union-find的人的最多页面,这里是详细的解决方案.

Find-Union是一个非常快速的操作,在几乎不变的时间内执行.
它遵循Jeremie对路径压缩和跟踪集合大小的见解.对每个查找操作本身进行路径压缩,从而获得lg *(n)的摊销时间. lg *就像逆Ackerman函数,生长非常慢,很少超过5(至少直到n <2 ^ 65535).联合/合并集执行懒惰,只需将1根指向另一个根,特别是较小的集合的根到较大集的根,它在不间断的时间完成. 请参考以下代码@L_404_0@

  1. class UF {
  2. int *id,cnt,*sz;
  3. public:
  4. // Create an empty union find data structure with N isolated sets.
  5. UF(int N) {
  6. cnt = N; id = new int[N]; sz = new int[N];
  7. for (int i = 0; i<N; i++) id[i] = i,sz[i] = 1; }
  8. ~UF() { delete[] id; delete[] sz; }
  9.  
  10. // Return the id of component corresponding to object p.
  11. int find(int p) {
  12. int root = p;
  13. while (root != id[root]) root = id[root];
  14. while (p != root) { int newp = id[p]; id[p] = root; p = newp; }
  15. return root;
  16. }
  17. // Replace sets containing x and y with their union.
  18. void merge(int x,int y) {
  19. int i = find(x); int j = find(y); if (i == j) return;
  20. // make smaller root point to larger one
  21. if (sz[i] < sz[j]) { id[i] = j,sz[j] += sz[i]; }
  22. else { id[j] = i,sz[i] += sz[j]; }
  23. cnt--;
  24. }
  25. // Are objects x and y in the same set?
  26. bool connected(int x,int y) { return find(x) == find(y); }
  27. // Return the number of disjoint sets.
  28. int count() { return cnt; }
  29. };

如果您愿意,请投票或接受.

猜你在找的C&C++相关文章