Как реализовать Union-Find с помощью связанных списков? - PullRequest
Новая
       24

Как реализовать Union-Find с помощью связанных списков?

0 голосов
/ 23 июня 2019

Мне нужно написать кусок кода, используя алгоритм Крускала, который, в свою очередь, нуждается в алгоритме Union-Find.

Это включает в себя методы Make-Set (x), Find-Set (x) иСоюз (х, у).Мне нужно реализовать их, используя связанные списки, но я не уверен, как начать с метода Make-Set.

Метод Make-Set должен создать набор и превратить первый элемент в ключ (длясравнить наборы).Как именно я объявил бы ключ, используя связанные списки?

Вкратце: как мне реализовать этот псевдокод для связанных списков в Java?

Make-Set (x) xp =x

x.rank = 0

Спасибо за вашу помощь заранее!

1 Ответ

0 голосов
/ 24 июня 2019

Я слышал, что это упоминалось в прошлом не как «Союз-Поиск», а как непересекающийся набор. Это не совсем связанный список, поскольку узлы действительно имеют ссылку, но они не обязательно связаны линейно. Это больше похоже на дерево, где каждый узел имеет указатель на своего родителя, и вы можете пройти по дереву к корню.

Сейчас у меня не так много времени, но вот краткий набросок того, как бы я реализовал это в Java: 

class Disjoint {
    Disjoint next;

    Disjoint findSet() {
        Disjoint head = this;
        if (next != null) {
            head = next.findSet();
            next = head;
        }
        return head;
    }

    void union(Disjoint other) {
        Disjoint us = this.findSet();
        Disjoint them = other.findSet();
        us.next = them;
    }
}

Создание экземпляра - это ваш Make-Set. То, что вы называете Find-Set, я бы назвал найти голову или найти лидера, может быть, найти личность. Я назвал это findSet здесь, хотя. Он идет по цепочке, чтобы найти корень дерева. Он также выполняет необязательную операцию; он возвращает все ссылки на обратном пути из рекурсивного вызова, чтобы они все указывали прямо на корень. Это оптимизация для того, чтобы цепочки были короткими.

Наконец, объединение реализуется просто путем назначения указателя next одного корня, чтобы он указывал на другой набор. Я не уверен, что вы намеревались с rank; если это размер набора, вы можете добавить поле для этого и просто суммировать их, когда объединяете два набора. Но вы инициализируете его на 0 для нового набора, когда я ожидаю, что он будет инициализирован на 1.

Два узла a и b принадлежат одному и тому же набору, если a.findSet() == b.findSet(). Если вам нужны узлы для переноса некоторых данных, сделайте класс универсальным, предоставьте данные конструктору и добавьте геттер: 

class Disjoint<T> {
    Disjoint<T> next;
    T data;

    public Disjoint(final T data) {
        this.data = data;
    }

    public T getData() {
        return data;
    }

    // rest of class identical except Disjoint replaced with Disjoint<T> everywhere

}
...