Как хранить каждый набор в лесу непересекающихся наборов?

Пытаюсь сам закодировать это на Java... Я создал класс GraphNode для представления узлов, у которых есть указатель на их родителя.

Я также создал класс DisjointSet, который включает метод MakeSet, который создает объект GraphNode и ссылается на себя в родительской ссылке.

Вопрос в том, как мне сохранить каждый узел, чтобы я мог легко получить к нему доступ позже в Union и FindSet? Сначала я подумал, что нужно сохранить его в BST, но мне пришлось бы создать собственный класс TreeNode, который хранит не только значение, но и ссылку на GraphNode. Есть ли более простой способ?


java data-structures disjoint-sets
person user1956609    schedule 24.02.2014    source источник

Ответы (1)


arrow_upward
8
arrow_downward

Есть совсем более простой способ: забыть обо всех нодовых делах. Узлы просто концептуальны, их не обязательно реализовывать буквально, да и проще не делать.

Все, что вам нужно, это два массива целых чисел. Тот, в котором хранятся родители, и тот, в котором хранятся ранги. Таким образом, в псевдокоде это будет выглядеть примерно так:

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]++;
            }
        }
    }
}
person harold    schedule 25.02.2014