CODEWITHSUNDEEP
javadata-structuresdisjoint-sets
user1956609
user1956609

Reputation: 2202

How to store each set in a disjoint-set forest?

Trying to code this up myself in Java... I have created a GraphNode class to represent nodes that have a pointer to their parent.

I have also created a DisjointSet class that includes a MakeSet method that creates a GraphNode object and has its parent reference refer to itself.

The question is: how do I then store each node so I can easily access it later in Union and FindSet? My first thought it to store it in a BST, but I'd have to create a custom TreeNode class that stores not only the value, but also the reference to the GraphNode. Is there an easier way?

Upvotes: 0

Views: 2958

Answers (1)

user555045
user555045

Reputation: 64904

There is absolutely an easier way: forget about all the node-business. The nodes are just conceptual, it's not required to implement them literally, and it's easier not to.

All you need is two arrays of ints. One that stores the parents and one that stores the ranks. So in a sort of pseudo-code, it would look something like this:

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: 8

Related Questions