Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 120
Текст из файла (страница 120)
В данной главе мы познакомимся со структурой данных, которая поддерживает эти операции. В разделе 21.1 описаны операции, поддерживаемые указанной структурой данных, и представлено простое приложение. В разделе 21.2 мы рассмотрим использование простого связанного списка для представления связанных множеств.
Более эффективное представление при помощи деревьев приведено в разделе 21.3. Время работы с использованием деревьев линейно для всех практических применений, хотя теоретически оно сверхлинейно. В разделе 21.4 определяется и обсуждается очень быстро растущая функция и ее очень медленно растущая инверсия, которая и проявляется во времени работы операций над представлением непересекающихся множеств с использованием деревьев.
Там же при помощи амортизационного анализа доказывается верхняя сверхлинейная граница времени работы. Часть Ч. Сложные структуры данных 582 21.1 Операции над непересекающимися множествами Структура данных для нелересекающихся множеств (йз)о1п1-зе1 да1а зГшсШге) поддерживает набор о = (Ям Яз,..., Бь) непересекающихся динамических множеств. Каждое множество идентифицируется лредставителем (тергезеп1абяе), который представляет собой некоторый член множества.
В ряде приложений не имеет значения, какой именно элемент множества используется в качестве представителя; главное, чтобы при запросе представителя множества дважды, без внесения изменений в множество между запросами, возвращался один и тот же элемент. В других приложениях может действовать предопределенное правило выбора представителя, например, наименьшего члена множества (само собой разумеется, в предположении о возможности упорядочения элементов множества). Как и в других изученных нами реализациях динамических множеств, каждый элемент множества представляет некоторый объект. Обозначим объект через х. Мы хотим обеспечить поддержку следующих операций.
МАкл Бет(х) создает новое множество, состоящее из одного члена (который, соответственно, является его представителем) х. Поскольку множества непересекающиеся, требуется, чтобы х не входил ни в какое иное множество. 1)ьпон(х, у) обьединяет динамические множества, которые содержат х и у (обозначим их через Я н Як), в новое множество. Предполагается, что до выполнения операции указанные множества не пересекались. Представителем образованного в результате множества является произвольный элемент Б 0 0 Ят хотя многие реализации операции Умом выбирают новым представителем представителя множества Я или Як. Поскольку нам необходимо, чтобы все множества были непересекающимися, операция 1)н1ом должна уничтожать множества Я и Яю удаляя их из коллекции 'э'.
Рпчо Блт(х) возвращает указатель на представителя (единственного) множества, в котором содержится элемент х. В этой главе мы проанализируем зависимость времени работы структуры данных для непересекающихся множеств от двух параметров: количества операций МАкп Бит и и общего количества операций МАкп Бет, 1)н1он и г|но Бет т. Поскольку множества непересекающиеся, каждая операция ()ьпом уменьшает количество множеств на 1. Следовательно, после и — 1 операций Пилон останется только одно множество, так что количество операций 1)н|ом не может превышать и — 1. Заметим также, что поскольку в общее количество операций ги включены операции Млкп Бит, то ги > и. Предполагается также, что и операций МАкп Бвт являются первыми и выполненными операциями. Глава 21. Структуры данных для непересекающихся множеств 583 Приложение структур данных для непересекающихся множеств Одно из многих применений структур данных для непересекающихся множеств — в задаче об определении связных компонентов неориентированного графа (см.
раздел Б.4). Так, на рис. 21.1 показан граф, состоящий из четырех связных компонентов — (а, Ь,с,г(), (е,2,д), (гз,з) и (Д. |ау-- — — ~а1 Рис. 21.1. Граф с четырьмя связными компонентами Процедура Соххестеп Сомрохехтз, приведенная ниже, использует операции над непересекающимися множествами для вычисления связных компонентов графа. После того как процедура Соххестеп Сомрохехтз разобьет множество вершин графа на непересекающиеся множества, процедура БАМЕ СОМРОХЕХТ может определить, принадлежат ли две данные вершины одному и тому же связному компоненту'. (Множество вершин графа С обозначим как Ъ' [С1, а множество ребер — как Е [С).) СОХХЕСТЕО СОМРОХЕХТЗ(ья) 1 1ог Каждая вершина и Е 1г[ь ') 2 по МАке Зет(п) 3 1ог Каждое ребро (и, и) Е Е[гя1 4 Йо и Р!х0 Бет(ы) у- Р!хР Бет(п) 5 Феп 13Х1ОХ(и, и) ЗАМЕ СОМРОХЕХТ(и, и) 1 И Р!ХО БЕТ(и) = Р!ХР БЕТ(п) 2 Феп гегнгп ТИОЕ 3 ене гегпгп РАЬЗЕ Процедура СОххестеп СОмРОхехтз сначала помещает каждую вершину и в ее собственное множество.
Затем для каждого ребра (и, и) выполняется объединение множеств, содержащих и и н. В соответствии с упражнением 21.1-2, после 'Если ребра графа являются "статическими", те, не изменяются с течением времени, то вычислить связные компоненты можно быстрее при помоцзи поиска в глубину (см, упражнение 22,3-11). Однако иногда ребра добавляются "динамически" и нам надо поддерживать связные компоненты при лобавлении нового ребра. В этой ситуации приведенная здесь реализация оказывается эффективнее, чем повторное выполнение поиска вглубь для каждого нового ребра. 584 Часть Ч.
Сложные структуры данныи Таблица 21.1. Набор непересекающихся множеств в процессе вычислений обработки всех ребер две вершины будут находиться в одном связном компоненте тогда и только тогда, когда соответствующие объекты находятся в одном множестве. Итак, процедура Соннестеп СОМРОнентз вычисляет множества так, что процедура ЯАме СОмРОхент может определить, находятся ли две вершины в одном и том же связном компоненте. В табл. 21.1 показан процесс вычисления непересекающихся множеств процедурой Сомместеп СомРОнентз. В реальной реализации описанного алгоритма представления графа и структуры непересекающихся множеств требуют наличия взаимных ссылок, т.е.
объект, представляющий вершину, должен содержать указатель на соответствующий объект в непересекающемся множестве и наоборот. Эти детали программной реализации зависят от используемого для реализации языка программирования и здесь не рассматриваются. Упражнения 2!.1-1. Предположим, что процедура Соннестер СОМРОнентз вызывается для неориентированного графа С = (Ъ;Е), где 1' = (а, Ь,с,Н,е,г",д, Ь,г, т', Ц, а ребра из Е обрабатываются в следующем порядке: (Н,1), (1', Ь), (д,й), (Ь, д), (а, Ь), (г, з), (Н, й), (Ь, Я, (Н, 1'), (д, т), (а, е), (г, Н). Перечислите вершины в каждом связном компоненте после выполнения каждой итерации в строках 3-5.
21.1-2. Покажите, что после того, как все ребра будут обработаны процедурой Соннестеп СОМРОнентз„две вершины находятся в одном связном компоненте тогда и только тогда, когда они находятся в одном и том же множестве. 21.1-3. Сколько раз вызывается процедура Г1нО Яет в процессе выполнения про- цедуры Соьлчестеп СОМРОнентз над неориентированным графом С = Глава 21. Структуры данных для непересекающихся множеств 585 = (1Г, Е) с lс связными компонентами? Сколько раз вызывается процедура Ун1он? Выразите ваш ответ через ~Ц, (Е~ и 1г. 21.2 Представление непересекающихся множеств с помощью связанных списков Простейший способ реализации структуры данных для непересекающихся множеств — с помощью связанных списков.
Первый объект в каждом связанном списке является его представителем. Каждый объект в связанном списке содержит член множества, указатель на обьект, содержащий следующий член множества, и указатель на представителя. Каждый список поддерживает указатель ЬеаН на представителя и указатель 1а11 — на последний объект в списке. На рис. 21.2а показаны два множества. Внутри каждого связанного списка объекты могут располагаться в произвольном порядке (однако мы считаем, что первый объект в каждом списке является его представителем).
Г ,.-+-, ил / Рис. 21.2. Представление двух множеств с помощью связанного списка и их объ- единение Часть Ч. Сложные структуры данньц 58б При использовании такого представления процедуры МАке Бет и р!хп 8ет легко реализуются и время их работы равно О (1). Процедура МАке Бег(х) создает новый связанный список с единственным обьектом х, а процедура г 1ып Бет просто возвращает указатель на представителя множества. Простая реализация объединения Простейшая реализация операции Пыю1ч при использовании связанных спнсюв требует гораздо больше времени, чем процедуры МАке Бет или Р1ып 8ет. Как показано на рис. 21.2б, мы выполняем процедуру Пы1о1ч(х, у), добавляя список с элементом х в юнец списка, содержащего у. указатель 1ая списка с элементом у используется для того, чтобы быстро определить, куда следует добавить списоК содержащий х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
