Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 147
Текст из файла (страница 147)
В алгоритме Крускала множество А является лесом. В А добавляются безопасные ребра, которые являются ребрами минимального веса, объединяющими два различных компонента. В алгоритме Прима множество А образует единое дерево. В А добавляются Часть И. Алгоритмы для работы с графами 668 1 14 (в) 8,-, 7 9 14 Щ „, )О г,) (г) (в] 8 4 г ф" (х) а 11, .'(а: 9 14 Е) (е) 'а .
(О 9 (О Рис. 23.4. Применение алгоритма Крусквла к графу, показанному на рис. 23Л. Залприхованные ребра принадлежат растущему лесу А. Алгорипя рассматривает ребра в порвдке возрастания их веса На каждом шаге алгоритма стрелка указывает на рассматриваемое ребро. Если ребро обьединяет два различных дерева леса, оно добавляется в лес, тем самым сливая зги деревья в одно. безопасные ребра, которые являются ребрами минимального веса, соединяющи- ми дерево с вершиной вне дерева.
Алгоритм Крускала Алгоритм Крускала находит безопасное ребро для добавления в растущий лес путем поиска ребра (и, и) с минимальным весом среди всех ребер, соединяющих два дерева в лесу. Обозначим два дерева, соединяемые ребром (и, о), как С1 и Сз. Поскольку (и,о) должно быть легким ребром, соединяющим С) с некоторым другим деревом, из следствия 23.2 вытекает, что (и, и) — безопасное для С) ребро.
Алгоритм Крускада является жадным, поскольку на каждом шаге он добавляет к лесу ребро с минимально возможным весом. Наша реализация алгоритма Крускала похожа на алгоритм для вычисления связных компонентов из раздела 21.1. Она использует структуру для представления непересекающихся множеств. Каждое из множеств содержит вершины неко- Глава за Миннтнмьныв вставные деленна ббР 8вл, 7 РЪ =-, .
'.4) 7'' 6 1 ' " 7 7 л,,я Г10 10 гь Эгвгнвывва 'я ' 8 ЛО Рис. 23.4 (ираявлгаение1. Завершение выполнения алгоритма Крусаала. торого дерева в текущем лесу. Операция Р1нп-БЕТ(и) возвращает представитель множествгь содержащего и. Таким образом, мы можем определить, принадлежат ли вершины и и н одному и тому же дереву, проверив равенство РпчпБЕТ(и) и Р1МП-БЕТ(е). Объединение деревьев выполняется с помощью процедуры Ш410м. МБТ-Ккт7екАь(С, 07) 1 А=6 2 Тог каждой вершины н Е С.
К 3 МАКЕ-БЕТ(0) 4 Отсортировать ребра С.Е в неуменьшающемся порядке по весу в 5 Рог каждого ребра (и, 0) Е С. Е в этом порядке 6 11 Р1740-Бет(и) ~ Р!ггп-Бет(0) 7 А = А17((и,п)) 8 131410Н(и, О) 9 гегвгп А Работа алгоритма Крускала показана на рис. 23.4. В строках 1-3 выполняется инициализация множества А пустым множеством и создаются ~Ъ'~ деревьев, каждое из которых содержит по одной вершине. В строке 4 ребра в Е сортируются согласно их весу в неубывающем порядке. Цикл Рог в строках 5 — 8 проверяет для каждого ребра (и, 0) в указанном неубывающем по весу порядке, принадлежат ли его концы и и н одному н тому же дереву. Если это так, то данное ребро не может быть добавлено к лесу без того, чтобы создать при этом цикл, поэтому в таком б70 Часть Гй Алгоритмы для работы с графами случае ребро отбрасывается.
В противном случае, когда концы ребра принадлежат разным деревьям, в строке 7 ребро (и, с) добавляется в множество А, и вершины двух деревьев объединяются в строке 8. Время работы алгоритма Крускала для графа С = (17, Е) зависит от реализации структуры данных для непересекающихся множеств. Мы будем считать, что лес непересекающихся множеств реализован так, как описано в разделе 21.3, с эвристиками объединения по рангу и сжатия пути, поскольку асимптотически это наиболее быстрая известная реализация. Инициализация множества А в строке 1 занимает время 0(1), а время, необходимое для сортировки множества в строке 4, равно О(Е!8 Е) (стоимость (Ц операций Млкп-Бит в цикле 1ог в строках 2 и 3 мы учтем чуть позже).
Цикл 1ог в строках 5 — 8 выполняет 0(Е) операций ЕпчпВьт и Уьцох над лесом непересекающихся множеств. Вместе с ~Ц операциями млкп-Япт зта работа требует времени 0((17+ е) сг(17)), где о — очень медленно растущая функция, определенная в разделе 21.4. Поскольку мы предполагаем, что С вЂ” связный граф, справедливо соотношение (Е) > ٠— 1, так что операции над непересекающимися множествами требуют времени 0(Е сг(17)). Кроме того, поскольку сь(~Ъ'~) = 0(18 К) = 0(18Е), общее время работы алгоритма Крускала равно 0(Е 18 Е). Заметим, что )Е) < Щ~, поэтому 18 )Е~ = 0(18 К) н время работы алгоритма Крускала можно записать как О(Е 18 17), Алгоритм Прима Как и алгоритм Крускала, алгоритм Прима представляет собой частный случай обобщенного алгоритма поиска минимального остовного дерева из раздела 23.1.
Алгоритм Прима очень похож на алгоритм Дейкстры для поиска кратчайшего пути в графе, который будет рассмотрен в разделе 24.3. Алгоритм Прима обладает тем свойством, что ребра в множестве А всегда образуют единое дерево. Как показано на рис.23.5, дерево начинается с произвольной корневой вершины т и растет до тех пор, пока не охватит все вершины в К. На каждом шаге к дереву А добавляется легкое ребро, соединяющее дерево и отдельную вершину из оставшейся части графа. Согласно следствию 23.2 данное правило добавляет только безопасные для А ребра; следовательно, по завершении алгоритма ребра в А образуют минимальное остовное дерево.
Данная стратегия является жадной, поскольку на каждом шаге к дереву добавляется ребро, которое вносит минимально возможный вклад в общий вес. Для эффективной реализации алгоритма Прима необходим быстрый способ выбора нового ребра для добавления в дерево. В приведенном ниже псевдокоде в качестве входных данных алгоритму передаются связный граф С и корень г минимального остовного дерева, которое будет "выращено" алгоритмом.
В процессе работы алгоритма все вершины, которые не входят в дерево, располагаются в невозрастающей очереди с приоритетами Я, основанной на значении атрибута )сер. Для кюкдой вершины о значение атрибута е. Йеу представляет собой минимальный вес среди всех ребер, соединяющих е с вершиной в дереве. Если ни одного такого ребра нет, считаем, что п.
Йеу = оо. Атрибут о.л указывает родителя о в дереве. В процессе работы алгоритма множество А из процедуры Глава 23. Миямкальиме оояовлие Деревья у' '~ь (г) ( г ба )о (я) (в] Рнс, 23.5. Применение алгоритма Прима к графу, показанному на рнс.23.1, Корневой вершиной явшсюя вершина а. Заштрнховвнные ребра пршмдлежвт растущему дереву; черным цветом показаны вершины, иаходмцнеся в этом дереве. На кшкдой нтерацин алгоритма вершины дерева определяют разрез )рафа, н к дереву добавляется лепое ребро, пересекающее разрез. Нмгрнмер, на второй итерации шпорнтм может выбрать лнбо ребро (6, с), либо ребро (а,(г), поскольку оба онн явмпотся легкими рсбрамн, пересекающими разрез.
б72 Часть ~7. Алгоритмы длл работы с графами бпмпкгс-МБТ неявно поддерживается как А = ((и, и.я): с б 17 — (т) — Я) Когда алгоритм завершает работу, очередь с приоритетами Я пуста и минималь- ным остовным деревом для С является дерево А = ((и, илг): и Е 1' — (т)) МЯТ-Ркгм(С, ш,т) 1 1ог каждой вершины и е С. К 2 и.)сеу = оо 3 и.я = мн. 4 т.lсеу = О 5 Я=С.т' 6 «Ы$еЯ ФИ 7 и = Ехтклст-Мпя(Я) 8 Гог каждой вершины и е С. Аг(7'[и) 9 И и й Я и ш(и, и) < и. йеу 10 и.гг = и 11 и. Гсеу = иг(и, и) // С вызовом 13псквлзп-Кку(Я, и, ш(и, и)) Работа алгоритма Прима проиллюстрирована на рис. 23.5. В строках 1-5 ключи всех вершин устанавливаются равными оо (кроме корня т, ключ которого равен О, так что он оказывается первой обрабатываемой вершиной), указателям на родителей для всех узлов присваиваются значения ьг11 и все вершины вносятся в неубывающую очередь с приоритетами 9.
Алгоритм поддерживает следующий инвариант цикла, состоящий из трех частей. Перед каждой итерацией цикла «'пйе в строках 6-11 1. А = ((и, и. я): и Е Ъ' — (т) — Гьг); 2. вершины, уже помещенные в минимальное остовное дерево, принадлежат множеству $' — Я; 3. для всех вершин и е г,г справедливо следующее: если т.п ф мп., то и.
)сеу < оо и и, )сеу — вес легкого ребра (и, и. я), соединяющего и с некоторой вершиной, уже находящейся в минимальном остовном дереве. В строке 7 определяется вершина и Е Я, инцидентная легкому ребру, пересекающему разрез (17 — Я, Я) (за исключением первой итерации, когда и = т в соответствии с присвоением в строке 4). Удаление и из множества Я добавляет ее в множество 17 — Я вершин дерева, таким образом добавляя (и, и.я) в А.
Цикл Гог в строках 8 — 11 обновляет атрибуты lсеу и гг каждой вершины и, смежной с и и не находящейся в дереве. Это обновление сохраняет третью часть инварианта. Время работы алгоритма Прима зависит от выбранной реализации невозрастающей очереди с приоритетами г3. Если реализовать ее как бинарную пирамиду 673 Глава 33. Минииаеиные вотивные деревьв (см. главу б), то для выполнения инициализации в строках 1 — 5 за время 0(Ъ') можно использовать процедуру Вгцьп-М1м-Нелр. Тело цикла эеЬйе выполняется ~Ц раз, а поскольку каждая операция Ехтклст-Мцч занимает время 0(18 К), общее время всех вызовов процедур Ехтклст-Мнч составляет 0(У 18 У). Цикл Гог в строках 8-11 выполняется всего 0(Е) раз, поскольку сумма длин всех списков смежности равна 2 ~Е~.
Внутри цикла Гог проверка на принадлежность Я в строке 9 может быть реализована за постоянное время, если воспользоваться для каждой вершины битом, указывающим, находится ли она в ф и обновлять этот бит при удалении вершины из Я. Присвоение в строке 11 неявно включает операцию 13искилзк-Кит над пирамидой. Время выполнения этой операции в бинарной пирамиде — 0(18 $'). Таким образом, общее время работы алгоритма Прима составляет 0(У 18 17 + Е 18 Ъ') = 0(Е 18 У), что асимптотически совпадает со временем работы рассмотренной ранее реализации алгоритма Крускала. Асимптотическое время работы алгоритма Прима можно улучшить за счет применения фибоначчиевых пирамид. В главе 19 показано, что если Щ элементов организованы в фибоначчиеву пирамиду, то операцию Ехстлкст-М1ы можно выполнить за амортизированное время 0(18 У), а операцию Вискилзп-Кит (для реализации строки 11) — за амортизированное время 0(1).
Следовательно, при использовании фибоначчиевой пирамиды для реализации неубывающей очереди с приоритетами Я общее время работы алгоритма Прима улучшается до 0(Е+ 1718~ ). Упражнении гз.г г Алгоритм Крускапа может возвращать разные остовные деревья для одного и того же входного графа С в зависимости от взаимного расположения ребер с одинаковым весом при сортировке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
