在不相交的集合數據結構中實現路徑壓縮？

這是我的一個不相交集的Objective-C實現。 - 正數指向父。 - 負數表示根子&兒童數。（所以它們每個都在-1處開始脫節。） - 索引用作我正在分組的數據。似乎工作正常...只是有幾個問題。在不相交的集合數據結構中實現路徑壓縮？

找到：如何壓縮路徑？因爲我沒有遞歸執行它，所以我必須存儲路徑，並在查找根後再次循環設置它？
加入：我基於加入兒童數而不是深度！？我想這是不對的。如果深度相等，我需要在連接過程中做些特別的事情嗎？

謝謝。

DisjointSet.h

@interface DisjointSet : NSObject 
{ 
    NSMutableArray *_array; 
} 

- (id)initWithSize:(NSInteger)size; 
- (NSInteger)find:(NSInteger)item; 
- (void)join:(NSInteger)root1 root2:(NSInteger)root2; 

@end

DisjointSet.m

#import "DisjointSet.h" 

@implementation DisjointSet 

- (id)initWithSize:(NSInteger)size 
{ 
    self = [super init]; 
    if (self) 
    { 
     _array = [NSMutableArray arrayWithCapacity:size]; 
     for (NSInteger i = 0; i < size; i++) 
     { 
      [_array addObject:[NSNumber numberWithInteger:-1]]; 
     } 
    } 
    return self; 
} 

- (NSInteger)find:(NSInteger)item 
{ 
    while ([[_array objectAtIndex:item] integerValue] >= 0) 
    { 
     item = [[_array objectAtIndex:item] integerValue]; 
    } 
    return item; 
} 

- (void)join:(NSInteger)root1 root2:(NSInteger)root2 
{ 
    if (root1 == root2) return; 

    NSInteger data1 = [[_array objectAtIndex:root1] integerValue]; 
    NSInteger data2 = [[_array objectAtIndex:root2] integerValue]; 
    if (data2 < data1) 
    { 
     [_array setObject:[NSNumber numberWithInteger:data2 + data1] atIndexedSubscript:root2]; 
     [_array setObject:[NSNumber numberWithInteger:root2] atIndexedSubscript:root1]; 
    } 
    else 
    { 
     [_array setObject:[NSNumber numberWithInteger:data1 + data2] atIndexedSubscript:root1]; 
     [_array setObject:[NSNumber numberWithInteger:root1] atIndexedSubscript:root2]; 
    } 
} 

@end

來源

2013-01-06 Rakka Rage

對於查找操作，不需要存儲路徑（與您的_array分開）或使用遞歸。這些方法都需要O（P）存儲（P =路徑長度）。相反，你可以遍歷兩次路徑。第一次，你找到根。第二次，您將所有孩子設置爲指向根。這需要O（P）時間和O（1）存儲。

- (NSInteger)findItem:(NSInteger)item { 
    NSInteger root; 
    NSNumber *rootObject = nil; 
    for (NSInteger i = item; !rootObject;) { 
     NSInteger parent = [_array[i] integerValue]; 
     if (parent < 0) { 
      root = i; 
      rootObject = @(i); 
     } 
     i = parent; 
    } 

    for (NSInteger i = item; i != root;) { 
     NSInteger parent = [_array[i] integerValue]; 
     _array[i] = rootObject; 
     i = parent; 
    } 

    return root; 
}

合併操作，要存儲每一根的排名（這是它的深度的上限），而不是每個樹根的後裔數量。存儲每個根的等級允許您將較短的樹合併到較高的樹中，這保證了查找操作的O（log N）時間。當被合併的樹具有相同的等級時，等級僅增加。

- (void)joinItem:(NSInteger)a item:(NSInteger)b { 
    NSInteger aRank = -[_array[a] integerValue]; 
    NSInteger bRank = -[_array[b] integerValue]; 
    if (aRank < bRank) { 
     NSInteger t = a; 
     a = b; 
     b = t; 
    } else if (aRank == bRank) { 
     _array[a] = @(-aRank - 1); 
    } 

    _array[b] = @(a); 
}

來源

2013-01-06 18:16:38

「NSInteger bRank = - [_ array [a] integerValue];」應該是「[b]」？謝謝 –

和我想它（joinItem，否則）將「aRank - 1」如果存儲排名作爲一個負面的根... ...？無論如何，再次感謝 –

是的。我糾正了你指出的錯誤。 –

你一定要使用遞歸執行路徑壓縮。我甚至不會考慮試圖非遞歸地做到這一點。

實現分離集數據結構應該非常容易，並且可以在幾行中完成。它很容易將它從僞代碼翻譯成任何編程語言。您可以在Wikipedia上找到僞代碼。（不幸的是，我不能讀Objective-C，所以我不能真正判斷你的代碼是否正確）。

來源

2013-01-06 18:02:42 kokx

是的。要實現無遞歸的最高祖先壓縮，您需要維護自己的列表。讓一個傳遞鏈來獲得指針，這些指針需要改變它們的父指針，並且學習根。然後進行第二遍更新必要的父指針。

遞歸方法正在做同樣的事情。第一遍是遞歸的「清盤」，它在程序堆棧中存儲需要父指針更新的集合。隨着遞歸展開，第二遍是相反的。

我不同於那些說遞歸方法總是最好的人。在合理數量的系統（尤其是嵌入式系統）中，程序堆棧的大小是有限的。有些情況下，在查找之前，許多聯合會連續執行。在這種情況下，對於n個元素，母鏈的大小可以是O（n）。這裏通過遞歸摺疊可以將堆棧炸燬。由於你在Objective C中工作，這可能是iOS。我不知道那裏的默認堆棧大小，但如果使用遞歸，值得一看。它可能比你想象的要小。 This article意味着512K的輔助線程和1Mb的主線程。

迭代，不斷替代空間

其實我寫的主要原因是要指出，你仍然對於n ammortized操作獲得爲O（log^* N） - 只是一個陰影小於效率（1） - 如果你只做二分因子壓縮：在查找操作中，改變父指針，以便它們指向祖父母而不是根指針。這可以在恆定存儲中迭代完成。 This lecture at Princeton對此算法進行了討論，並在5行C的循環中實現它。請參見幻燈片29.

來源

2013-01-06 18:18:15 Gene

在不相交的集合數據結構中實現路徑壓縮？

回答

相關問題