Алгоритмы - построение и анализ (1021735), страница 133
Текст из файла (страница 133)
Алгоритм Прима обладает тем свойством, что ребра в множестве А всегда образуют единое дерево. Как показано на рис. 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 неявно включает операцию Рпскпдзп Кпу над пирамидой. Время выполнения этой операции — 0 (18 1г). Таким образом, общее время работы алгоритма Прима составляет 0 (~'!8 1г + Е 18 ~") = О (Е 18 'г'), что асимптотически совпадает со временем работы рассмотренного ранее алгоритма Крускала. Однако асимптотическое время работы алгоритма Прима можно улучшить за счет применения фибоначчиевых пирамид. В главе 20 показано, что если Щ элементов организованы в фибоначчиеву пирамиду, то операцию Ехстлкст Мпч можно выполнить за амортизированное время О (1кЪ'), а операцию РескеАБе Кпу — за амортизированное время 0 (1).
Следовательно, при использовании фибоначчиевой пирамиды для реализации очереди с приоритетами Я общее время работы алгоритма Прима улучшается до 0 (Е+ У 18 1г). Упражнения 23.2-1. Алгоритм Крускала может возвращать разные остовные деревья для одного и того же входного графа О в зависимости от расположения ребер с одинаковым весом при сортировке.
Покажите, что для любого минимального остовного дерева Т графа С можно указать способ сортировки 657 Глава 23. Минимальные остовные деревья ребер С, для которого алгоритм Крускала даст минимальное остовное дерево Т. 23.2-2. Предположим, что граф С = (К Е) представлен при помощи матрн- цы смежности. Разработайте простую реализацию алгоритма Прима для этого случая, время работы которой равно 0 (1'з). 23.2-3. Будет ли реализация алгоритма Прима с использованием фибоначчиевых пирамид асимптотически быстрее реализации с использованием бинарных пирамид для разреженного графа С = (1; Е), где ~Е~ = 0(1')? А для плотного графа, в ютором ~Е1 = 9 (Уз)? Каким образом должны быть связаны (Е~ и )Ц, чтобы реализация с использованием фибоначчиевых пирамид была быстрее реализации с использованием бинарных пирамид? 23.2-4.
Предположим, что все веса ребер графа представляют собой целые чис- ла в диапазоне от 1 до ~1'1 Насколько быстрым можно сделать алгоритм Крускала в этом случае? А в случае, югда вес каждого ребра представляет собой целое число в диапазоне от 1 до И' для некоторой константы И'? 23.2-5. Предположим, что вес каждого из ребер графа представляет собой це- лое число в диапазоне от 1 до ~Ц. Насколью быстрым можно сделать алгоритм Прима в этом случае? А в случае, когда вес любого ребра представляет собой целое число в диапазоне от 1 до И' для некоторой константы Иг? Предположим, что веса ребер графа равномерно распределены на по- * 23.2-6. луоткрытом интервале [О, 1). Какой алгоритм — Крускала или Прима— будет работать быстрее в этом случае? Предположим, что граф С имеет уже вычисленное минимальное остов- * 23.2-7. ное дерево.
Насколько быстро можно обновить минимальное остовное дерево при добавлении в С новой вершины и инцндентных ребер? Профессор предложил новый алгоритм декомпозиции для вычисления 23.2-8. минимальных остовных деревьев, заключающийся в следующем. Для данного графа С = ('1Г, Е) разбиваем множество вершин И на два подмножества Ъ'~ и Уз, таких что Я~ и Щ отличаются не более, чем на 1. Пусть Е1 — множество ребер, инцидентных только над вершинами в 1~м а Ез — множество ребер, инцидентных толью над вершинами в Из. Рекурсивно решаем задачу поиска минимальных остовных деревьев в каждом их подграфов С1 = Я,Ез) и Сз = Я,Ез), а затем выбираем среди ребер Е ребро с минимальным весом, пересекающее разрез Я, Уз), и используем его для обьединения двух полученных минимальных остовных деревьев в одно.
Докажите или опровергните корректность описанного алгоритма поиска минимального остовного дерева. Часть Ч1. Алгоритмы для работы с графами 658 Задачи 23-1. Второе минимальное остовное дерево С = (К Е) — неориентированный связный граф с весовой функцией ю: Š— В; предположим, что [Е[ > [Ц и что веса всех ребер различны. Определим второе минимальное остовное дерево следующим образом. Пусть Т вЂ” множество всех остовных деревьев С, и пусть Т' — минимальное остовное дерево С. Тогда вторым минимальным остовнмм деревам (зесопд-Ьезг пппппшп зраппш8 Згее) будет такое дерево Т, что ю (Т) = пппупет 1з ) (ш (Т )).
а) Покажите, что минимальное остовное дерево единственное, но вторых минимальных остовных деревьев может быть несколько. б) Пусть Т вЂ” минимальное остовное дерево С. Докажите, что существуют ребра (и, с) йТ и (х, у) ф Т, такие что Т вЂ” ((и, с) )0((х, у))— второе минимальное остовное дерево С. в) Пусть Т вЂ” остовное дерево С, и пусть для любых двух вершин и, с е У шах [и,е[ — ребро максимального веса на единственном пути между и и и в Т. Разработайте алгоритм, который за время О (Уз) для данного Т вычисляет шах [и, и] для всех и, с е У. г) Разработайте эффективный алгоритм вычисления второго минимального остовного дерева С.
23-2. Минимальное остовное дерево разреженного графа Для очень разреженного связного графа С = (1;Е) можно добиться дальнейшего улучшения времени работы О (.Е + У 18 У) алгоритма Прима с использованием фибоначчиевых пирамид путем предварительной обработки С в целях уменьшения количества его вершин перед применением алгоритма Прима. В частности, для каждой вершины и мы выбираем инцидентное и ребро (и, о) с минимальным весом и помещаем это ребро в строящееся минимальное остовное дерево.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
