Find-Set(s) («найти множество»). Возвращает указатель на представитель (единственного) множества, содержащего элемент х.

11шсш(ж,?/) («объединение»). Применима, если элементы хну содержатся в различных множествах Sx и Sy, и заменяет эти множества на объединение SxL)Sy; при этом выбирается некоторый представитель для U. Сами множества Sx и Sy при этом удаляются.

В некоторых приложениях выбор представителя в множестве должен подчиняться каким-то правилам (например, элементы могут быть упорядочены и представителем является наименьший элемент множества). В любом случае существенно, что представитель множества не меняется, пока само множество остается неизменным.

В этой главе мы оценим время работы операций над системами непересекающихся множеств. Параметрами будут число операций Make-Set (то есть общее число элементов во всех множествах), которое мы обозначим через га, а также суммарное число операций Union, Make-Set и Find-Set, которое мы обозначим через то. Прежде всего заметим, что (по определению) то га, а также что число операций Union не превосходит га - 1 (после каждой из них количество множеств уменьшается на единицу).

Пример использования систем непересекающихся множеств

Применим системы непересекающихся множеств к задаче о связных компонентах неориентированного графа (см. раздел 5.4; пример графа с четырьмя связными компонентами дан на рис. 22.1а).

Алгоритм Connected-Components (связные компоненты), приведённый ниже, разбивает множество вершин графа на непересекающиеся множества, соответствующие связным компонентам; после этого можно с помощью процедуры Same-Component выяснить, лежат ли две данные вершины в одной компоненте. Если граф задан заранее («режим off-Нпе»), быстрее найти его связные компоненты с помощью поиска в глубину (упражнение 23.3-9); однако если граф строится постепенно и в любой момент надо уметь отвечать на вопрос, каковы его связные компоненты («режим оп-line»), то может оказаться выгоднее применить наш алгоритм, а не проводить заново поиск в глубину после добавления каждого из рёбер.

Ниже E[G] и V[G] обозначают множества соответственно рёбер и вершин графа G.

Connected-Components(G)

1for (для) каждой вершины v\in V[G]

2do Make-Set(v)

3for (для) каждого ребра (u,v) \in E[G]

4do if Find-Set(u)\ne Find-Set(v)

5then Union(u,v)

Рис. 22.1 (часть (б) я даже б-м нарисовал)

Рис. 22.1 22.1 а) Граф, состоящий из четырех связных компонент: {a,b,c,d}, {е, f,g}, {h, г} и {j}. б) Последовательные состояния системы непересекающихся множеств в процессе работы алгоритма connected-components.

Same-Component(u,v)

1if Find-Set(u)=Find-Set(v)

2then return true

3else return false

Алгоритм Connected-Components работает так. Сначала каждая вершина рассматривается как одноэлементное подмножество. Далее для каждого ребра графа мы объединяем подмножества, в которые попали концы этого ребра (рис. 22.16). Когда все рёбра обработаны, множество вершин разбивается на связные компоненты (упр. 22.1-2). Теперь процедура Same-Component определяет, лежат ли две данные вершины в одной связной компоненте, дважды вызвав процедуру Find-Set.

Упражнения

22.1-1

Следуя образцу рис. 22.1, опишите выполнение алгоритма Connected-Components для графа G, у которого V[G] =

{a,b,c,d,e,f,g,h,i,j,k}nE[G] = { (d,i), (/,&), (g,i), (b,g), (a,h),(d,k), (b,j), (d,f),

Рёбра обрабатываются в том порядке, в котором они выписаны. 22.1-2

Покажите, что алгоритм Connected-Components действительно находит связные компоненты графа. 22.1-3

Алгоритм Connected-Components применили к графу с v вершинами и е ребрами, состоящему из к связных компонент. Сколько при этом было вызовов процедур Find-Set и Union?

Рис. 22.2 Подпись:

а) Представление двух множеств с помощью списков. Представителем множества {Ь, с, е, h} является элемент с, представителем {d, /, д} является /. Каждый объект в списке содержит элемент множества, указатель на следующий элемент и указатель на представителя (то есть на начало списка), б) Результат выполнения операции Union(е,д). Представитель объединения множеств есть

22.2. Реализация с помощью списков

Самый простой вариант реализации системы непересекающихся множеств хранит каждое множество в виде списка. При этом представителем множества считается первый элемент списка, и каждый элемент списка содержит ссылки на следующий элемент списка и на первый элемент списка (который считается представителем списка). Для каждого списка мы храним указатели на его первый и последний элементы (второй из них нужен при добавлении элементов в конец списка). Порядок элементов в списке может быть любым. На рис. 22.2 (а) изображены два представленных таким образом множества.

При такой реализации операции Make-Set и Find-Set требуют времени 0(1): Make-Set создаёт список из одного элемента, а Find-Set возвращает указатель на начало списка.

Простейшая реализация объединения

При естественной реализации операция Union оказывается дорогостоящей. Выполняя UNlON(a:,?/), мы добавляем список, содержащий ж, к концу списка, содержащего у (рис. 22.2 Ь). Представителем нового множества при этом будет начало нового списка, то есть представитель множества, содержащего у. При этом нужно ещё установить правильные указатели на начало списка для всех бывших элементов множества, содержащего ж, и время на выполнение этой операции линейно зависит от размера указанного множества.

Легко привести пример, в котором время выполнения квадратично зависит от числа операций (рис. 22.3). Пусть даны га элементов Ж1,Ж2,.. - ,хп. Выполним операции Маке-8ет(ж8) для всех г = 1, 2,..., га, а затем га - 1 операций Unioni, х2), Union2, жз), ... , Union(хп 1, хп). Поскольку стоимость операции Union(жг-, Xi+\) пропорциональна г, суммарная стоимость выполнения 2га - 1 one-