java - 如何将每个集合存储在不相交的集合森林中？

Question

尝试自己用 Java 编写代码...我创建了一个 GraphNode 类来表示具有指向其父级的指针的节点。

我还创建了一个 DisjointSet 类，其中包含一个 MakeSet 方法，该方法创建一个 GraphNode 对象并使其父引用引用自身。

问题是:如何存储每个节点，以便稍后可以在 Union 和 FindSet 中轻松访问它？我首先想到的是将其存储在 BST 中，但我必须创建一个自定义 TreeNode 类，它不仅存储值，还存储对 GraphNode 的引用。有没有更简单的方法？

Answer 1

绝对有一种更简单的方法:忘记所有节点业务。这些节点只是概念性的，不需要从字面上实现它们，而且不这样做更容易。

您所需要的只是两个整数数组。一种存储 parent ，另一种存储排名。因此，在某种伪代码中，它看起来像这样:

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