Сжатие путей в Union-Find

В функции find системы непересекающихся множеств можно выполнять сжатие путей, чтобы быстрее находить корневой узел узла. Для дерева множества многие узлы могут быть присоединены под его корневым узлом. Поэтому во время процесса find мы можем попытаться переместить узел вверх как можно выше, снизу вверх, если текущий посещаемый узел не является корневым, тем самым уменьшая глубину дерева. Этот процесс называется сжатием путей.

Как показано на рисунке ниже, процесс find(4) может использовать сжатие путей, чтобы уменьшить количество уровней в дереве.

Когда узел 4 ищет вверх корневой узел, первый шаг сжатия уменьшает количество уровней дерева на один:

Узел 2 также ищет вверх и не является корневым узлом, поэтому направьте элемент 2 на родителя его исходного родительского узла. После этой операции количество уровней дерева соответственно уменьшается на один, и возвращается корневой узел 0.

Измените код процесса find на:

// процесс find, найти номер множества, соответствующего элементу p
// сложность O(h), h — высота дерева
private int find(int p){
    assert( p >= 0 && p < count );

    // сжатие пути 1
    while( p != parent[p] ){
        parent[p] = parent[parent[p]];
        p = parent[p];
    }
    return p;

}

Описанное выше сжатие пути не является оптимальным подходом. Мы можем сжать исходное дерево до формы, показанной на рисунке ниже, которая имеет минимальное количество уровней.

Этот процесс find можно представить так:

...
// процесс find, найти номер множества, соответствующего элементу p
// сложность O(h), h — высота дерева
private int find(int p) {
    assert (p >= 0 && p < count);

    // Второй алгоритм сжатия пути
    if (p != parent[p])
        parent[p] = find(parent[p]);
    return parent[p];
}
...

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

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

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

package example.union;

/**
* Оптимизация на основе ранга
 */
public class UnionFind4 {

    private int[] rank;   // rank[i] представляет количество уровней дерева, представленного множеством с корнем в i
    private int[] parent; // parent[i] представляет родительский узел, на который указывает i-й элемент
    private int count;    // количество элементов данных

    // конструктор
    public UnionFind4(int count){
        rank = new int[count];
        parent = new int[count];
        this.count = count;
        // инициализация: каждый parent[i] указывает на самого себя, что означает, что каждый элемент образует отдельное множество
        for( int i = 0 ; i < count ; i ++ ){
            parent[i] = i;
            rank[i] = 1;
        }
    }

    // процесс 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;

        // Второй алгоритм сжатия пути
        //if( p != parent[p] )
        //parent[p] = find( parent[p] );
        //return parent[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;

        if( rank[pRoot] < rank[qRoot] ){
            parent[pRoot] = qRoot;
        }
        else if( rank[qRoot] < rank[pRoot]){
            parent[qRoot] = pRoot;
        }
        else{ // rank[pRoot] == rank[qRoot]
            parent[pRoot] = qRoot;
            rank[qRoot] += 1;   // поддерживать значение rank
        }
    }
}
Другие расширения