algorithm - O(1) 在不相交的集合数据结构中创建、查找、并集

Question

今天，由于this slide的第13页，我与某人讨论了Kruskal最小生成树算法。 .

演示文稿的作者说，如果我们使用(双向)链表实现不相交的集合，Make 和Find 的性能将为 O(1 ) 和 O(1)。 Union(u,v)操作的时间是min(nu,nv)，其中nu和nv是存储 u 和 v 的集合的大小。

我说过我们可以通过使每个成员的表示指针指向一个定位器来将 Union(u,v) 的时间缩短为 O(1)包含指向集合的真实表示的指针。

在 Java 中，数据结构如下所示:

class DisjointSet {
    LinkedList<Vertex> list = new LinkedList<Vertex>(); // for holding the members, we might need it for print

    static Member makeSet(Vertex v) {
        Member m = new Member();

        DisjointSet set = new DisjointSet();
        m.set = set;
        set.list.add(m);

        m.vertex = v;

        Locator loc = new Locator();
        loc.representation = m;
        m.locator = loc;

        return m;
    }
}

class Member {
    DisjointSet set;
    Locator locator;
    Vertex vertex;

    Member find() {
        return locator.representation;
    }

    void union(Member u, Member v) { // assume nv is less than nu
        u.set.list.append(v.set.list); // hypothetical method, append a list in O(1)
        v.set = u.set;
        v.locator.representation = u.locator.representation;
    }

}

class Locator {
    Member representation;
}

对于简约代码感到抱歉。如果可以这样做，那么每个不相交的集合操作(​​Make,Find,Union)的运行时间将为 O(1)。但是与我讨论过的人看不到改进。我想知道您对此的看法。

还有 Find/Union 在各种实现中最快的性能是什么？我不是数据结构方面的专家，但通过快速浏览互联网，我发现没有恒定时间数据结构或算法可以做到这一点。

Answer 1

我的直觉与您的同事一致。你说:

u.set.list.append(v.set.list);//假设的方法，在 O(1) 中追加一个列表

看起来您的意图是通过追加完成合并。但是，要实现 Union，您必须删除重复项才能使结果成为一个集合。因此，我可以看到用于固定 集大小的 O(1) 算法，例如...

Int32 set1;
Int32 set2;

Int32 unionSets1And2 = set1 | set2;

但这让我觉得是作弊。如果您针对 N 的一般情况执行此操作，我看不出您如何避免某种形式的迭代(或散列查找)。这将使它成为 O(n)(或最多 O(log n))。

仅供引用:我很难遵循您的代码。在 makeSet 中，您构造一个永远不会逃脱函数的本地定位器。它看起来并不像它做任何事情。并且不清楚您在附加中的意图是什么。可能需要编辑和详细说明您的方法。