Union-Find: быстрый поиск

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

Запросить ID множества элемента и вернуть его напрямую.idзначение массива,O(1)временная сложность.

...
private int find(int p) {
    assert p >= 0 && p < count;
    return id[p];
}
...

Объединить множества, к которым принадлежат элементыpи элементq. Процесс объединения требует обхода всех элементов, затем объединения ID множеств двух элементов. Этот процесс имеет...O(n)сложность.

...
public void unionElements(int p, int q) {
    int pID = find(p);
    int qID = find(q);
    if (pID == qID)
        return;
    for (int i = 0; i < count; i++)
        if (id[i] == pID)
            id[i] = qID;
}
...

Пример кода на Java

Исходный пакет:Скачать

код файла UnionFind1.java:

package example.union;

/**
* Первая версия union-Find
 */

public class UnionFind1 {
    // Наша первая версия Union-Find по сути представляет собой массив
    private int[] id;
    // количество элементов данных
    private int count;

    public UnionFind1(int n) {
        count = n;
        id = new int[n];
        // Инициализация: каждый id[i] указывает на самого себя, нет объединённых элементов
        for (int i = 0; i < n; i++)
            id[i] = i;
    }

    // процесс find, найти номер множества, соответствующего элементу p
    private int find(int p) {
        assert p >= 0 && p < count;
        return id[p];
    }

    // проверить, принадлежат ли элемент p и элемент q одному и тому же множеству
    // Сложность O(1)
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    // объединить множества, содержащие элемент p и элемент q
    // Сложность O(n)
    public void unionElements(int p, int q) {

        int pID = find(p);
        int qID = find(q);

        if (pID == qID)
            return;

        // Процесс объединения требует однократного обхода всех элементов и объединения ID множеств двух элементов
        for (int i = 0; i < count; i++)
            if (id[i] == pID)
                id[i] = qID;
    }
}
Другие расширения