Структуры данных и модели вычислений
Операции над разделенными множествами
Разделенные множества — это абстрактный тип данных, предназначенный для представления коллекции, состоящей из некоторого числа попарно непересекающихся подмножеств
заданного множества . Для простоты в качестве
будем рассматривать множество .
Этот тип данных применяется в таких задачах, как поиск минимального остовного дерева для заданного взвешенного неориентированного графа, построение компонент связности графа, минимизация конечного автомата, и многих других, требующих динамического поддержания некоторого отношения эквивалентности. Примеры таких задач будут рассмотрены ниже.
Как правило, в таких задачах вычисления начинаются с пустой коллекции подмножеств (). Затем по мере вычислений формируются новые подмножества, включаемые в коллекцию. Формирование новых подмножеств происходит либо путем создания одноэлементного подмножества, либо путем объединения уже существующих в коллекции подмножеств. Для осуществления таких действий используются имена включенных в коллекцию подмножеств. В качестве имени подмножества будем использовать один из его элементов (главный элемент), выбираемый по определенному правилу. Поскольку в коллекции всегда будут находиться попарно непересекающиеся подмножества множества , такое имя будет однозначно определять требуемое подмножество.
СОЗДАТЬ(). Эта операция предназначена для введения в коллекцию нового подмножества, состоящего из одного элемента , при этом предполагается, что не входит ни в одно из подмножеств коллекции, созданной к моменту выполнения этой операции. Элемент указывается в качестве параметра. Именем созданного подмножества будет считаться сам элемент .
ОБЪЕДИНИТЬ(). С помощью этой операции можно объединить два подмножества коллекции, имеющие, соответственно, имена и , в одно новое подмножество, при этом оба объединяемые подмножества удаляются из коллекции, а вновь построенное подмножество получает некоторое имя. Во всех рассматриваемых нами случаях именем нового полученного в результате этой операции подмножества будет одно из имен или .
