2

这是我对不相交集的 Objective-C 实现。- 正数指向父母。- 负数表示根数和子数。（所以它们每个都从 -1 开始脱节。） - 索引充当我正在分组的数据。似乎工作正常......只是有几个问题。

  1. find：如何压缩路径？因为我不是递归地做，我是否必须存储路径并在找到根目录后再次循环设置？

  2. 加入：我是基于儿童数量而不是深度加入！？我想这是不对的。如果深度相等，我是否需要在加入期间做一些特别的事情？

谢谢。

不相交集.h

@interface DisjointSet : NSObject
{
    NSMutableArray *_array;
}

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

@end

不相交集.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
4

3 回答 3

4

对于查找操作，无需存储路径（与您的 分开_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-06T18:16:38.097 回答
1

您绝对应该使用递归来实现路径压缩。我什至不会考虑尝试以非递归方式进行。

实现 disjoin-set 数据结构应该非常容易，并且可以用几行代码完成。将其从伪代码转换为任何编程语言非常非常容易。您可以在Wikipedia上找到伪代码。（不幸的是，我无法阅读 Objective-C，所以我无法真正判断您的代码是否正确）。

于 2013-01-06T18:02:42.480 回答
1

是的。要在没有递归的情况下实现最高祖先压缩，您需要维护自己的列表。让一个通过链来获取指向需要更改其父指针的集合的指针，并学习根。然后进行第二次传递以更新必要的父指针。

递归方法也在做同样的事情。第一遍是递归的“结束”，它将需要父指针更新的集合存储在程序堆栈上。随着递归展开，第二遍是相反的。

我与那些说递归方法总是最好的人不同。在合理数量的系统（尤其是嵌入式系统）中，程序堆栈的大小是有限的。在某些情况下，在查找之前连续执行了许多联合。在这种情况下，对于 n 个元素，父链的大小可以是 O(n)。这里通过递归折叠可能会炸毁堆栈。由于您在 Objective C 中工作，因此这可能是 iOS。我不知道那里的默认堆栈大小，但是如果您使用递归，则值得一看。它可能比你想象的要小。 本文暗示辅助线程为 512K，主线程为 1Mb。

迭代的、恒定的空间替代方案

实际上，我写这篇文章的主要原因是指出，对于 n 次摊销操作，您仍然会得到 O(log^* n) - 只是比折叠效率低，而且仍然有效 O(1) - 如果你只这样做因子二压缩：在查找操作中，更改父指针，使它们指向祖父母而不是根。这可以通过在常量存储中迭代来完成。 普林斯顿大学的这个讲座讨论了这个算法，并用 5 行 C 循环实现了它。见幻灯片 29。

于 2013-01-06T18:18:15.883 回答