處理Union-Find與很多對象的算法

Question

我有一個問題（不再與stackoverflow（hehe））當試圖實現UnionFind結構算法與路徑壓縮時找到算法。

我有整數的標準數組，數組可以變得相當大 - >它工作正常，直到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 int find(int i) { 
     while (i != id[i]){ 
      id[i] = id[id[i]]; 
      i = id[i];    
     }  
    return i; 
    } 

和尾recrusion：

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; 
} 

我在查找嘗試迭代的方式：

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元素，更多的則是足夠的爲了解決我的問題。

我打電話測試工會這樣的：

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，...），我的測試算法將停止工作。

我有縮小它在查找功能相關的問題，很可能是與路徑壓縮

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

Answer 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]; 
    } 
} 

Answer 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--; 
    } 
} 

Answer 3

Union-Find數據結構通常包含兩種不同的優化。一種是路徑壓縮。你有。

但是，其他優化發生在一個聯盟，在那裏你仔細選擇兩個根中的哪一個做另一個的孩子，通常是通過聯盟排名或聯盟規模。通過這種優化，您的樹不應該足夠深以導致堆棧溢出。但是，您的統一功能似乎缺少了這種優化。