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