如何实现由链表不相交集的数据结构？ [英] How to implement a Disjoint-set data structure by Linked list？

问题描述

我不知道如何通过链表来Implemente不相交集数据结构？谁可以告诉我吗？ 我特别感到困惑如何查找集（）可以工作O（1）时间，这样的实现。THX〜

i don't know how to Implemente Disjoint-set data structure by Linked list？ who can tell me？ i'm especially confused about how can the find-set（） can work O(1) time in such implementation。 thx~

推荐答案

虽然不相交集数据结构通常被解释为对本之木，它通常实施使用数组：一个数组的索引映射到指数的父母和一个阵列映射的索引，它的等级。此摆脱了很多无谓的开销（在空间和时间），这是不相关的理论，但它是在实际中。您可能需要一种方法来某种对象的索引和实例之间的映射。

While the disjoint-set data structure is typically explained as a forest of trees, it's typically implemented with arrays: one array to map an index to the index of its parent, and one array to map an index to its rank. This gets rid of a lot of pointless overhead (in both space and time), which isn't relevant in theory, but it is in practice. You may need a way to map between the indexes and instances of some kind of object.

查找不为O（1），由工作方式。跟了上来prevents诀窍查找采取线性时间，但它仍然可以在最坏的情况下步骤的对数数。在O（α（n））的时间是摊销的时间，它的棘手解释它从何而来 - 你可以找到分析的效率不错，但不是线性并集算法[的Tarjan]

find does not work in O(1), by the way. The trick with the ranks prevents find from taking linear time, but it can still take a logarithmic number of steps in the worst case. The O(α(n)) time is an amortized time, and it's tricky to explain where it comes from - you can find the analysis in Efficiency of a Good But Not Linear Set Union Algorithm [Tarjan].

下面是它可以工作的一种方式：

Here's one way it could work:

disjoint_set {
    int[] parent, rank;
    makeset(int n)
    {
        rank = new int[n];
        parent = new int[n];
        for(int i = 0; i < n; i++)
            parent[i] = i;
    }

    int find(int i)
    {
        if (parent[i] != i)
            parent[i] = find(parent[i]);
        return parent[i];
    }

    void union(int x, int y)
    {
        x_root = find(x);
        y_root = find(y);
        if (x_root != y_root) {
            if (rank[x_root] < rank[y_root])
                parent[x_root] = y_root;
            else if (rank[x_root] > rank[y_root])
                parent[y_root] = x_root;
            else {
                parent[y_root] = x_root;
                rank[x_root]++;
            }
        }
    }
}

这篇关于如何实现由链表不相交集的数据结构？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！