- Система непересекающихся множеств
-
Система непересекающихся множеств позволяет администрировать множество элементов, разбитое на непересекающиеся подмножества. При этом каждому подмножеству назначается его представитель — элемент этого подмножества. Абстрактная структура данных определяется множеством трех операций {Union, Find, MakeSet}.
Содержание
Использование
Система непересекающихся множеств очень удобна для хранения компонент связности в графах. К примеру, Алгоритму Краскала необходима подобная структура данных для эффективной реализации.
Определение
Пусть конечное множество, разбитое на непересекающиеся классы :
- .
Каждому классу назначается представитель . Соответствующая система непересекающихся множеств поддерживает следующие операции:
- MakeSet(): создает для элемента новый класс. Назначает этот же элемент представителем созданного класса.
- Union(, ): объединяет оба класса, принадлежащие представителям и , и назначает представителем нового класса.
- Find(): определяет для класс к которому принадлежит элемент, и возвращает его представителя.
Алгоритмическая реализация
Тривиальная реализация сохраняет принадлежность элементов из и представителей в индексном массиве. На практике же, чаще используются множества деревьев. Это позволяет существенно сократить время, необходимое для операции Find. При этом представитель записывается в корень дерева, а остальные элементы класса в узлы под ним.
- Union(, ): Вешает корень более низкого дерева под корень более высокого дерева. Если при этом становится ребенком , оба узла меняются местами.
- Find(): проходит путь от до корня дерева и возвращает его (корень в данном случае является представителем).
Эвристики
Для ускорения операций Union и Find используются следующие эвристики.
Union-By-Size
Во время операции Union(r, s) корень более низкого дерева вешается под корень более высокого дерева. Благодаря этому подходу сохраняется балансировка дерева. Глубина каждого поддерева T не может превысить величину . При использовании этой эвристики worst-case-время операции Find уменьшается с до . Для эффективной реализации предлагается сохранять в корне количество узлов в дереве.
Сжатие путей
Используется чтобы ускорить операцию Find(). При каждом новом поиске, все элементы находящиеся на пути от корня до искомого элемента, вешаются под корень дерева. В этом случае операция Find будет работать в среднем α(n), где α - функция, обратная функции Аккермана. Это позволяет значительно ускорить работу, так как α для всех применяемых на практике значений принимает значение, меньшее 5.
Пример реализации
Реализация на C++
const int MAXN = 1000; int p[MAXN], rank[MAXN]; void MakeSet(int x) { p[x] = x; rank[x] = 0; } int Find(int x) { return ( x == p[x] ? x : p[x] = Find(p[x]) ); } void Union(int x, int y) { if ( (x = Find(x)) == (y = Find(y)) ) return; if ( rank[x] < rank[y] ) p[x] = y; else p[y] = x; if ( rank[x] == rank[y] ) ++rank[x]; }
Ссылки
Категория:- Структуры данных
Wikimedia Foundation. 2010.