java – 处理具有大量对象的Union-Find算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了java – 处理具有大量对象的Union-Find算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2089字，纯文字阅读大概需要3分钟。

内容图文

我有一个问题(不再使用stackoverflow(hehe))尝试使用路径压缩实现UnionFind结构算法时查找算法.

我有标准的int数组,数组可以变得很大 – >它工作正常,直到60.000.000元素.

我的联盟功能如下所示：

public void unite(int p, int q) {
    if(p >= 0 && p < id.length && q >= 0 && q < id.length){
        if (isInSameSet(p, q)) return;
        id[find(p)] = find(q); 
        stevilo--;
    }
}

我的isInSameSet看起来像这样：

    public boolean isInSameSet(int p, int q) {
        if(p >= 0 && p < id.length && q >= 0 && q < id.length) 
            return find(p) == find(q);
        return false;
}

我在Find中尝试了迭代方式：

    public int find(int i) {
        while (i != id[i]){
            id[i] = id[id[i]];
            i = id[i];              
        }       
    return i;
    }

和尾巴后退：

    public int find(int i) {    
        int p = id[i];
        if (i == p) {
          return i;
        }
        return id[i] = find(p);     
     }

我的代码中有什么错过的吗？有没有其他方法来解决这类问题？

@edit：为代码添加构造函数：

    public UnionFind(int N) {
        stevilo = N;
        id = new int[N];        
        for(int i = 0; i < N; i++){
            id[i] = i;
        }

@ edit2(更好的解释和新发现)：
问题不在于stackoverflow不再是60.000.000元素,这足以解决我的问题.

我打电话给这样的测试工会：

for(i=0;i<id.length-1;i++)
unite(i,i+1)

所以结束对是这样的：

0:1, 1:2, 2:3, 3:4,.. 

这只是测试手段的最佳选择的唯一例子:)

然后我检查0的代表是否是表中的最后一个元素(99个表示100个元素)并且它有效.

问题是,我的算法只有在初始元素各自都在它们自己的并集中时才有效(0：0,1：1,2：2,3：3).如果我已经设置了不同的联盟(0：2,1：6,2：1,3：5,……),我的测试算法将停止工作.

我已将其缩小到Find函数中的问题,可能与路径压缩有关

id[i] = id[id[i]].

解决方法:

我曾经为UnionFind编写了一个算法,其时间复杂度为O(log *(n)).那是n的迭代对数.该算法在继续连接节点以提高效率时压缩树的路径.我发现它非常有效,尽管我没有对巨大的阵列大小进行实际测试.这是代码：

public class UnionFind
{
  private int[] id;

  public UnionFind(int capacity)
  {
    id = new int[capacity];
    for (int i = 0; i < capacity; i++)
    {
      id[i] = i;
    }
  }

  public boolean isConnected(int p, int q)
  {
    return root(p) == root(q);
  }

  public void connect(int p, int q)
  {
    if (isConnected(p, q))
    {
      return;
    }

    id[root(p)] = root(q);
  }

  private int root(int p)
  {
    int temp = p;

    if (p != id[p] && id[id[p]] != id[p])
    {
      while (p != id[p])
      {
        p = id[p];
      }

      id[temp] = id[p];
    }

    return id[p];
  }
}

内容总结

以上是互联网集市为您收集整理的java – 处理具有大量对象的Union-Find算法全部内容，希望文章能够帮你解决java – 处理具有大量对象的Union-Find算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---