4

我在尝试使用路径压缩实现 UnionFind 结构算法时遇到问题（不再使用 stackoverflow（呵呵））查找算法。

我有标准的整数数组，数组可以变得非常大->它可以正常工作，直到 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（更好的解释和新发现）：对于少于 60.000.000 个元素，问题不再存在于 stackoverflow 中，这足以解决我的问题。

我这样称呼测试联盟：

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

所以结尾对是这样的：

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

这只是测试手段的最优化选项的唯一示例:)

然后我检查 0 的代表是否是表中的最后一个元素（100 个元素为 99）并且它有效。

问题是，我的算法只有在初始元素都在它们自己的联合中时才有效（0:0、1:1、2:2、3:3）。如果我已经设置了不同的联合（0:2、1:6、2:1、3:5，...），我的测试算法将停止工作。

我已将其缩小为查找功能中的问题，可能与路径压缩有关

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

3 回答 3

2

一个小的优化是摆脱 isInSameSet ...

public void unite(int p, int q) {
    if(p >= 0 && p < id.length && q >= 0 && q < id.length){
        int rootp = find(p);
        int rootq = find(q);
        if (rootp==rootq) return;
        id[rootp] = rootq; 
        stevilo--;
    }
}
于 2014-03-29T09:49:20.073 回答
2

Union-Find 数据结构通常包括两种不同的优化。一是路径压缩。你有那个。

但是另一种优化发生在联合期间，您通常通过 Union-By-Rank 或 Union-By-Size 仔细选择两个根中的哪一个来生成另一个的孩子。通过这种优化，您的树永远不会太深而导致堆栈溢出。但是，您的 unite 函数似乎缺少该优化。

于 2014-03-31T15:35:15.533 回答
1

我曾经为 写过一个算法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];
  }
}
于 2014-03-31T15:45:19.120 回答