Union-Find Quick Union

Для набора данных структура данных Union-Find в основном поддерживает две операции:

  • union(p,q) - Соединяет два элемента p и q вместе.

  • find(p)- Запрашивает, к какому множеству принадлежит элемент p.

  • isConnected(p,q)- Проверяет, связаны ли два элемента p и q.

В предыдущем подразделе мы использовалиidдля представления множества Union-Find в виде массива; временная сложность операции find при фактическом использовании составляетO(1), но эффективность соединения была невысокой.

В этом подразделе мы реализуем множество Union-Find другим способом. Рассматривайте каждый элемент как узел, который указывает на свой родительский узел, а корневой узел указывает на самого себя. Как показано на рисунке ниже, узел 3 указывает на узел 2, что означает, что 3 и 2 связаны; узел 2 сам является корневым узлом, поэтому он указывает на самого себя.

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

Если в этот момент выполнитьunion(4,3), то элемент 4 указывает на элемент 3:

Массив также изменяется соответствующим образом:

Чтобы определить, связаны ли два элемента, нужно лишь проверить, совпадают ли их корневые узлы.

Как показано на рисунке ниже, корневые узлы узла 4 и узла 9 оба равны 8, поэтому они связаны.

Чтобы связать два элемента, нужно лишь найти их соответствующие корневые узлы и соединить эти корневые узлы; тогда они станут связанными узлами.

Предположим, мы хотим соединить 6 и 4 на рисунке выше; нам нужно лишь направить корневой узел 5 узла 6 на корневой узел 8 узла 4.

Чтобы построить такую древовидную структуру, указывающую на родительские узлы, используйте массив для построения дерева, указывающего на родительские узлы; parent[i] представляет родительский узел, на который указывает элемент i.

...
private int[] parent;
private int count;  // количество элементов данных
...

Процесс поиска: чтобы найти номер множества, соответствующего элементу p, нужно последовательно запрашивать его родительский узел, пока не будет достигнут корневой узел. Корневой узел характеризуется условием parent[p] == p, сложность O(h), где h — высота дерева.

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

Чтобы объединить множества, к которым принадлежат элемент p и элемент q, найдите корневые узлы этих двух элементов соответственно и сделайте так, чтобы один корневой узел указывал на другой корневой узел; тогда два множества объединятся. Эта операция имеет временную сложность O(h), где h — высота дерева.

public void unionElements(int p, int q){
    int pRoot = find(p);
    int qRoot = find(q);
    if( pRoot == qRoot )
        return;
    parent[pRoot] = qRoot;
}

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

Загрузка пакета исходного кода:Скачать

Код файла UnionFind2.java:

package example.union;
/**
* Вторая версия UnionFind
 */
public class UnionFind2 {
    // Наша вторая версия Union-Find использует массив для построения дерева, указывающего на родительские узлы
    // parent[i] представляет родительский узел i-го элемента
    private int[] parent;
    private int count;  // количество элементов данных
    // конструктор
    public UnionFind2(int count){
        parent = new int[count];
        this.count = count;
        // инициализация: каждый parent[i] указывает на самого себя, что означает, что каждый элемент образует отдельное множество
        for( int i = 0 ; i < count ; i ++ )
            parent[i] = i;
    }
    // процесс find, найти номер множества, соответствующего элементу p
    // сложность O(h), h — высота дерева
    private int find(int p){
        assert( p >= 0 && p < count );
        // продолжаем обращаться к родительскому узлу, пока не достигнем корневого узла
        // признак корневого узла: parent[p] == p
        while( p != parent[p] )
            p = parent[p];
        return p;
    }
    // проверить, принадлежат ли элемент p и элемент q одному и тому же множеству
    // сложность O(h), h — высота дерева
    public boolean isConnected( int p , int q ){
        return find(p) == find(q);
    }
    // объединить множества, содержащие элемент p и элемент q
    // сложность O(h), h — высота дерева
    public void unionElements(int p, int q){
        int pRoot = find(p);
        int qRoot = find(q);
        if( pRoot == qRoot )
            return;
        parent[pRoot] = qRoot;
    }
}
Другие расширения