CODEWITHSUNDEEP
algorithmdata-structures
pzz201
pzz201

Reputation: 1

How to implement a Disjoint-set data structure by Linked list？

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~

Upvotes: 0

Views: 3892

Answers (2)

user555045
user555045

Reputation: 64904

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.

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

Upvotes: 6

Paul Hankin
Paul Hankin

Reputation: 58211

A disjoint set datastructure doesn't work in O(1) time for every operation. Instead, it works in O(1) time over a large number of operations.

Each node stores a pointer to its parent, and the representative element for each disjoint set is the node you get following parent pointers as far as possible. To get to O(1), you must collapse chains of parent nodes so that each element points to the head node whenever you are following parent links.

Here's some Python code that does all this. Note especially the second while loop in the head method: this is the key to making the datastructure work efficiently.

class Node:
    def __init__(self, value):
        self.value = value
        self.parent = None

    def head(self):
        head = self
        while head.parent:
            head = head.parent
        while self != head:
            self.parent, self = head, self.parent
        return head

    def union(a, b):
        if a.head() != b.head():
            a.head().parent = b.head()


nodes = [Node(i) for i in range(10)]
nodes[0].union(nodes[1])
nodes[0].union(nodes[2])

print set(node.head().value for node in nodes)

Upvotes: 1

Related Questions