Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 132
Текст из файла (страница 132)
Операции пад иеперееекаюптимиси множествами Структура данных для непересекающихся множеств (о)з)о)пьзе1 да1а яиасгше) поддерживает набор о = (Яы Яз,..., Яь) непересекающихся множеств. Каждое множество идентифицируется нредставнтелен (гергезеп1а11те), который представляет собой некоторый член множества. В одних приложениях не имеет значения, какой именно элемент множества используется в качестве представителя; главное, чтобы при запросе представителя множества дважды, без внесения изменений в множество между запросами, возвращался один и тот же элемент. В других приложениях может действовать предопределенное правило выбора представителя, например наименьшего члена множества (само собой разумеется, в предположении о возможности упорядочения элементов множества).
Как и в других изученных нами реализациях динамических множеств, каждый элемент множества представляет некоторый объект х. Мы хотим обеспечить поддержку следующих операций. Часть и Сложные сщрукщуры донных 598 МАКЕ-БЕТ(х) создает новое множество, состоящее из одного члена (который, соответственно, является его представителем) х. Поскольку множества непересекающиеся, требуется„чтобы х не входил ни в какое иное множество.
(ах)ох(х, у) обьединяет динамические множества, которые содержат х и у (обозначим их через о', и Яр), в новое множество. Предполагается, что до выполнения операции указанные множества не пересекались. Представителем образованного в результате множества является произвольный элемент Я 0 Яр, хотя многие реализации операции ()х)Ох выбирают новым представителем представителя множества Я, или Яр. Поскольку нам необходимо, чтобы все множества были непересекающимися, операция 1)х)Ох концептуально должна уничтожать множества Я, и Яр, удаляя их из коллекции Я. Р!ХО-ЯЕТ(х) возвращает указатель на представителя (единственного) множества, в котором содержится элемент х.
В этой главе мы проанализируем зависимость времени работы структуры данных для непересекающихся множеств от двух параметров; количества операций МАке-Бет и и общего количества операций МАке-бет, (Зх!Ох и Р!хп-Бег т. Поскольку множества непересекающиеся, каждая операция 1)х)Ох уменьшает количество множеств на 1. Следовательно, после и — 1 операций 1)х)Ох останется только одно множество, так что количество операций ()Х)ОХ не может превышать и — 1. Заметим также, что поскольку в общее количество операций т включены операции МАке-Бет, то т ) и. Предполагается также, что и операций МАкеЯЕТ являются первыми и выполненными операциями.
Приложение струкчур данных длн непересекающихся множеств Одно из многих применений структур данных для непересекающихся множеств — в задаче об определении связных компонентов неориентированного графа (см. раздел Б.4). Так, на рис. 21.1,(а) показан граф, состоящий из четырех связных компонентов.
Процедура Соххестеп-СОМРОхехтз, приведенная ниже, использует операции над непересекающимися множествами для вычисления связных компонентов графа. После того как процедура СОХХЕСТЕО-СОМРОХЕХТЗ разобьет множество вершин графа на непересекающиеся множества, процедура ЯАме-СОмРОхехт в состоянии определить, принадлежат ли две данные вершины одному и тому же связному компоненту). (Множество вершин графа С обозначим как С.
)У, а множество ребер — как С.Е.) Если ребра графа являются "статичеакимиз т,е, не изменяются а течением времени, то вычислить авязныс компоненты можно быатргм а помощью поиака в глубину 1см. упр, 22.3.12). Одныю иногда ребра дабажщюгся "динамически", к нам нужно поддерживать связные компоненты при добавлении нового ребра. В этой ситуюии лривсденнаа здесь реализации оказывается эффективнее, чем повторное выполнение поиске вотубь для каждого нового ребра.
Глана вб Смрузаннян данник дяя нснярссскающшся мнажсста (а) (б1 Рис. 21.1. (а) Граф с четырьмя связными яомпоиситами: (а, Ь, с, д), (с, з, д), (6, з» и (3). (б) Набор испсрсссяазоппоыя миожсств попас обработки каждого ребра. СО(чХЕСТЕГЗ-СОМРО(чисЗТЗ (С) 1 (ог каждой вершины и Е ск. Ь' 2 МАКЕ-БЕТ(и) 3 (ог каждого ребра (и, и) б С. Е 4 !Р Р(м0-Бет(и) Ф Р!нп-Бет(и) 5 (ЛПОМ(и, и) БАМЕ-СОМРОЫЕХТ(и, и) 1 Ы Р(нп-Бет(и) == Р(г((з-Бег(и) 2 гегигп тк((е 3 е(ае ге(пгп РАьЗЕ Процедура Соынесте(з-СОМРОнентб сначала помещает квкдую вершину и в ее собственное множеспю.
Затем для каждого ребра (и, и) выполняется обьединение множеств, содержащих и и и. В соответствии с упр. 21.1.2 после обработки всех ребер две вершины будут находиться в одном связном компоненте тоща и только тогда, когда соответствующие объекты находятся в одном множестве. Таким образом, процедура СОннесте(з-СОМРОыЕНТЗ вычисляет множества так, что процещра БАме-Сомрохент может определить, находятся ли две вершины в одном и том же связном компоненте. На рис. 21.1, (б) показан процесс вычисления непересекающихся множеств процедурой Сонместеп-СОМРОмемтб.
В реальной реализации описанного алгоритма представления графа и структуры непересекающихся множеств требуют наличия взаимных ссылок, т.е. обь- Часть и Сяансные структуры данные 000 ект, представляющий вершину, должен содержать указатель на соответствующий объект в непересекающемся множестве и наоборот. Зти детали программной реализации зависят от используемого для реализации языка программирования и здесь не рассматриваются. Упражнения 21.1.1 Предположим, что процедура Сохнестеп-СомРОментз вызывается для неориентированного графа С = (Ъ;Е), где 1с = (а,Ь,с,й,е,1',д,й,ю',1,Ц, а ребра из Е обрабатываются в следующем порядке: (Й, 1), (1, Й), (д, 1), (Ь, д), (о, л), (г, 3), (с(, /с), (Ь, 1), (и, 1), (д, т), (а, е). Перечислите вершины в каждом связном компоненте после выполнения каждой итерации в строках 3 — 5.
21.1.2 Покажите, что после того, как все ребра будут обработаны процедурой СОмхестеО-СОмРОхехтз, две вершины находятся в одном связном компоненте тогда и только тогда, когда они находятся в одном и том же множестве. 21.1.З Сколько раз вызывается процедура г|нп-Бег в процессе выполнения процедуры Соннестеп-Сомроментз над неориентированным графом С = (Г, Е) с lс связными компонентами? Сколько раз вызывается процедура 13ьпон? Выразите ваш ответ через (И, )Е( и к. 21.2. Представление непересекающихся множеств с помощью связанных списков На рис. 21.2, (а) показан простейший способ реализации структуры данных для непересекающихся множеств: каждое множество представлено своим связанным списком.
Объект каждого множества имеет атрибуты ЬеаН, указывающий на первый объект списка, и 1ае(, указывающий на последний обьект списка. Каждый объект списка содержит член множества, указатель на следующий объект в списке и указатель на объект множества. Обьекты в пределах каждого списка могут располагаться в любом порядке. Представителем множества является член в первом объекте списка. Прн использовании такого представления в виде связанных списков процедуры МАке-Бег и Р~нп-Бет легко реализуются и время их работы равно 0(1). Процедура МАКЕ-ЯЕт(х) создает новый связанный список с единственным объектом х, а процедура г1хп-Яет(х) просто следует по указателю на объект множества и возвращает член обьекга, на который указывает ЬеаЫ.
Например, на рис. 21.2„(а) вызов гпчп-Бег(д) вернет 1. Глава дй Сндгунтуры данньгх для непересекающихся множеств Рис. 21.2. (а) Представление двух мнвкесгв в виде связанных списков. Множество ог содержит члены г(, Г' и д, с предсгалнтлем У, а множество Яз содержит члены Ь, с, е и Ь, с представителем с. Каждый обьекг в списке содержит член множества, указатель на следующий объект в списке и ухвзатель на обьекз множества.
Кюкдый обьект множества имеет указатели Ьеад и Гагт на первый и последний обьекгы соответственно. (6) Результат операции ()игом(д, е), которая добавляет связанный список. содержащий е, к связанному списку, содержащему д. Представителем полученного в результате множества является /. Объект множества оз для списка е уничтожается. Простая реализация объединения Простейшая реализация операции ())чюи при использовании связанных списков требует гораздо больше времени, чем процедуры МАке-Яет и Рпчп-Бет. Как показано на рис.21.2,(б), мы выполняем процедуру ()н)О)ч(х, у), добавляя список с элементом х в конец списка, содержащего у. Представитель списка х становится представителем результирующего списка.
Мы используем указатель (аз( для списка с элементом х для того, чтобы быстро определить, куда следует добавить список, содержащий р. Поскольку все члены списка у обьединяются со списком х, можно уничтожить объект множества для списка у. К сожалению, требуется обновить указатель на объект множества для каждого объекта, исходно входящего в список у, что требует времени, линейно зависящего от длины списка у. На рис. 21.2, например, операция ())ч)о)ч(д, е) требует обновления указателей объектов Ь, с, е и 6. Действительно, нетрудно построить последовательность из гп операций над и объектами, которая требует 9(п ) времени. Предположим, что у нас есть объекты хз, хз,..., х„.
Мы выполняем последовательность из и операций Мдке-Бет, за которой следует последовательность из п — 1 операций (3)ч1о)ч, показанных на рис.21.3, так что т = 2п — 1. На выполнение п операций МАке-Бет мы тратим время 9(п). Поскольку г-я операция ())чю)ч обновляет з объектов, общее количество объектов, обновленных всеми и — 1 операциями 13)ч)о)ч, равно и-1 з = е)(пз) г=1 602 Часть и Сложные структуры доплыл Количество обновленных объектов Операция МАке-Яет(хт) МАке-Яет(хз) МАКЕ-ЯЕТ (Хп) ()мюм(хз, х,) Ш'110М (ХЗ, Х2) 1)м!Ом(ха, хз) 1)м1ом(х, х -1) и — 1 Рнс. 21.3.
Последовательность 2п — 1 операций над и обьеатамн, воторал требует 9(п~) времена (в среднем ез(п) на одну операцнзо) прн представленнн с использованием свлзаннмл спнсвов н простой реалнзацлн процедуры 1)к!он. Общее юличество операций равно 2п — 1, так что каждая операция в среднем требует для выполнения времени 9(п). Таким образом, амортизированное время выполнения операции составляет 9(п). Весовая эвристнка В наихудшем случае представленная реализация процедуры ()мюм требует в среднем б!(п) времени на один вызов, поскольку может оказаться, что мы присоединяем длинный список к юроткому н должны при этом обновить поля указателей на представителя всех членов длинного списка.
Предположим теперь, что каждый список включает также поле длины списка (которое легко поддерживается) и что мы всегда добавляем меньший список к большему (при одинаковых длинах порядок добавления не имеет значения). При такой простейшей весовой эвристике (зуезй)з)ес)-цл(оп Ьецпзг)с) одна операция ПМЮМ может потребовать время П(п), если оба множества имеют по П(п) членов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
