0

Java でこれを自分でコーディングしようとしています...親へのポインターを持つノードを表す GraphNode クラスを作成しました。

また、GraphNode オブジェクトを作成し、その親参照が自身を参照する MakeSet メソッドを含む DisjointSet クラスも作成しました。

問題は、後で Union と FindSet で簡単にアクセスできるように、各ノードをどのように保存すればよいかということです。最初は BST に格納することを考えていましたが、値だけでなく GraphNode への参照も格納するカスタム TreeNode クラスを作成する必要があります。もっと簡単な方法はありますか？

4

1 に答える 1

8

絶対に簡単な方法があります。すべてのノードビジネスを忘れてください。ノードは単なる概念的なものであり、文字通り実装する必要はありません。実装しない方が簡単です。

必要なのは、2 つの int の配列だけです。1 つは親を格納し、もう 1 つはランクを格納します。したがって、一種の擬似コードでは、次のようになります。

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]++;
            }
        }
    }
}
于 2014-02-25T11:02:36.803 に答える