Алгоритмы - построение и анализ (1021735), страница 134
Текст из файла (страница 134)
Затем мы выполняем сжатие по всем выбранным ребрам (см. раздел Б.4). Вместо того чтобы проводить сжатие по одному ребру, мы сначала определяем множества вершин, которые объединяются в одну новую вершину. Затем мы создаем граф, который должен был бы получиться в результате объединения этих ребер по одному, но делаем это путем "переименования" ребер соответственно множествам, в которых оказываются концы этих ребер.
При этом одинаково переименованными могут оказаться одновременно несколько ребер, и в таком случае в качестве результирующего рассматривается только одно ребро с весом, равным минимальному весу среди соответствующих исходных ребер. Глава 23. Минимальные остовные деревья 659 Изначально мы полагаем строящееся минимальное остовное дерево Т пустым, и для каждого ребра (и, и) е Е выполняем присвоения ог$9 [и, и] = = (и, и) и с [и, и] = ш(и, ю). Атрибут ог$д используется для ссылки на исходное ребро графа, которое связано с данным ребром в сжатом графе.
Атрибут с хранит вес ребра, и при сжатии его значение обновляется в соответствии с приведенной выше схемой выбора весов ребер. Процедура МБТ Кю11се получает в качестве входных параметров С, сг$д, с и Т, и возвращает сжатый граф С' и обновленные атрибуты ог$д' и с' для графа С'. Процедура также переносит ребра из С в минимальное остовное дерево Т. МБТ КЕ011СЕ(С, ог$9, с,Т) 1 1ог (Для) каждого и Е 'г'[С] 2 Йо татки] ЕА1 зе 3 МАКЕ БЕТ(и) 4 $аг (Для) каждого и Е ЦС] 5 $$о $Т тагй[и] = ТА1ле 6 $$1еп Выбираем ю Е А4[и] с минимальным с[и, и] 7 П1ч10х(и, ю) 8 Т - Т11(ог$9[и, ю]) 9 таге] +- татЬ[и] - ТК1/Е 1О ЦС'] +- (Р1х$1 Бет(и): и е У[С]) 11 Е[С'] — О 12 $ог (Для) каждого (х, у) Е Е[С] 13 $$о и ~ — Р1Н13 БЕТ(х) 14 — Р1н13 Бет(у) $$' (и, и) ЯЕ[С'] 16 $$$еп Е[С] "- Е[С] ~! ((и'")) 17 огни, ю] — огзд[х У] 18 с'[и,и] с[х у] !9 е!ве !1 с[х,у] < с'[и и] 20 $$$еп ог$9'[и, и] — ог$9[х у] 21 с'[и,и] - с[х У] 22 Строим списки смежности Аг$3 $ог С' 23 гегпгп С', ог$9', с' и Т а) Пусть Т вЂ” множество ребер, возвращаемое процедурой МБТ Кео11се, и пусть А — минимальное остовное дерево графа С', образованное вызовом МБТ Ри1м(С', с', г), где г — произвольная вершина из $г [С'].
Докажите, что Т 13 (ог$д' [х, у]: (х, у) Е А) представляет собой минимальное остовное дерево графа С. б) Докажите, что ['г" [С'][ < [г'[/2. 660 Часть Ч!. Алгоритмы для работы с графами в) Покажите, как реализовать процедуру МВТ Кнппсн так, чтобы время ее работы составляло О (Е). (Указание: воспользуйтесь простыми структурами данных.) г) Предположим, мы 1с раз применяем процедуру МБТ Кюпсн, используя полученные при очередном вызове С', ог)д' и с' в качестве входных данных для следующего вызова и накапливаем ребра в Т.
Покажите, что общее время выполнения всех к вызовов составляет О ()с Е). д) Предположим, что после к вызовов процедуры МБТ йюпсн мы применяем алгоритм Прима МБТ Рнм1С', с', г), где С' и с' получены в результате последнего вызова процедуры МЯТ Кюг!сн, а г— произвольная вершина из У [С']. Покажите, как выбрать к, чтобы общее время работы составило 01Е1к1яУ). Докажите, что ваш выбор )с минимизирует общее асимптотическое время работы. е) Для каких значений !Е~ (выраженных через !У!) алгоритм Прима с предварительным сжатием эффективнее алгоритма Прима без сжатия? 23-3. Узкое остовное дерево Назовем узким оставиым деревом (Ьоп!епеск зрапп!пя !гее) Т неориентированного графа С остовное дерево С, в котором наибольший вес ребра минимален среди всех возможных остовных деревьев, и этот вес называется значением узкого остовного дерева.
а) Докажите, что минимальное остовное дерево является узким остовным деревом. Из части а) следует, что поиск узкого остовного дерева не сложнее поиска минимального остовного дерева. В оставшейся части задачи мы покажем, что его можно найти за линейное время. б) Разработайте алгоритм, который для данного графа С и целого числа Ь за линейное время определяет, превышает ли значение узкого остовного дерева число Ь или нет.
в) Воспользуйтесь вашим алгоритмом из части б) как подпрограммой в алгоритме решения задачи поиска узкого остовного дерева за линейное время. (Указание: можно воспользоваться подпрограммой сжатия множеств ребер, как в процедуре МБТ йюпсн, описанной в задаче 23-2.) 23-4. Альтернативные алгоритмы поиска минимальных остовиых деревьев В этой задаче мы приведем псевдокоды трех различных алгоритмов. Каждый из них принимает в качестве входных данных граф и возвращает Глава 23.
Минимальные остовные деревья 661 множество ребер Т. Для каждого из алгоритмов требуется доказать, что Т является минимальным остовным деревом графа, или доказать, что это не так. Кроме того, опишите эффективную реализацию каждого из алгоритмов, независимо от того, вычисляет он минимальное остовное дерево или нет. а) Мм'вн МБТ А(с.,ю) 1 Сортируем ребра в невозрастающем порядке весов 2 Т+ — Е 3 1ог (Для) каждого ребра е в отсортированном порядке 4 йо!Г Т вЂ” (е) — связный граф 5 гйеп Т Т вЂ” (е) 6 гегнгп Т б) МАтвн МБТ В(С,ю) 1 Т+ — 11 2 1ог (Для) каждого ребра е в произвольном порядке 3 бо 1Г Т 0 (е) не имеет циклов 4 Феп Т вЂ” Т 0 (е) 5 геГпгп Т в) МАУВЕ МБТ С(а,ю) 1 Т+-6 2 Гог (Для) каждого ребра е в произвольном порядке 3 йоТ вЂ” Т0(е) 4 1Г Т имеет цикл с 5 гЬеп Пусть е' — ребро максимального веса в с 6 Т Т вЂ” (е') 7 гегпгп Т Заключительные замечания Книга Таржана (Тат)ап) [292] содержит превосходный обзор задач, связанных с поиском минимальных остовных деревьев, и дополнительную информацию о них.
История данной задачи изложена Грехемом (ОгаЬагп) и Хеллом (Не!1) [131]. Таржан указывает, что впервые алгоритм для поиска минимальных остовных деревьев был описан в 1926 году в статье Борувки (О. Вогйчка). Его алгоритм состоит в выполнении 0(1яЪ') итераций процедуры МБТ Кнгнэсе, описанной в задаче 23-2. Алгоритм Крускала описан в [195] в 1956 году, а алгоритм, известный как алгоритм Прима, — в работе Прима (Рпгп) [250], хотя до этого он был открыт Ярником (1агпрк) в 1930 году.
Часть Ч1. Алгоритмы для работы с графами Причина, по которой жадные алгоритмы эффективно решают задачу поиска минимальных остовных деревьев, заключается в том„что множество лесов графа образует матроид (см. раздел 16.4). Когда ~Е~ = П(Ъ'18У), алгоритм Прима, реализованный с использованием фибоначчиевых пирамил, имеет время работы О (Е). Для более разреженных графов использование комбинации идей из алгоритма Прима, алгоритмов Крускала и Борувки, вместе с применением сложных структур данных дало возможность Фредману (Ргедшап) и Таржану [98) разработать алгоритм, время работы которого равно О (Е 18' У). Габов (баЬотч), Галил (Пай)„Спенсер (Брепсег) и Таржан [102) усовершенствовали этот алгоритм, доведя время его работы до О (Е 18 18' 1').
Чазел (СЬахе1!е) [53) разработал алгоритм, время работы которого — О (Еа (Е, 1~)), где а(Е, 1') — функция, обратная функции Аккермана (см. главу 21). В отличие от перечисленных ранее, алгоритм Чазела не является жадным. С задачей поиска минимального остовного дерева связана задача проверки осюноелого дерека (зраппшй 1гее чег[бсайоп), в юторой для данного графа О = = (ч'", Е) и дерева Т С Е требуется определить, является ли Т минимальным остовным деревом С. Кинг (Кшй) [177) разработал алгоритм решения данной задачи за линейное время, основанный на работах Комлеса (Кош1оз) [188) и Диксона (131хоп), Рауха (КаисЬ) и Таржана [77). Все описанные выше алгоритмы детерминированные и относятся к модели на основе сравнений, описанной в главе 8.
Каргер (Кагйег), Клейн (К1еш) и Таржан [169) разработали ранломизированный алгоритм поиска минимальных остовных деревьев, математическое ожидание времени работы которого — О (Ъ'+ Е). Этот алгоритм использует рекурсию наподобие алгоритма с линейным временем работы из раздела 9.3: рекурсивный вызов для вспомогательной задачи определяет подмножество ребер Е', которое не может находиться ни в одном минимальном остовном дереве.
Другой рекурсивный вызов, работаюший с подмножеством Š— Е', строит минимальное остовное дерево. Алгоритм также использует идеи из алгоритмов Борувки и Кинга. Фредман н Виллард (тч1!!агд) [100) показали, как найти минимальное остовное дерево за время О (У+ Е) с использованием детерминированного алгоритма, не основанного на сравнениях. Их алгоритм предполагает, что данные представляют собой Ь-битовые целые числа и что память юмпьютера состоит из адресуемых Ь- битовых слов. ГЛАВА 24 Кратчайшие пути из одной вершины Водителю автомобиля нужно найти как можно более короткий путь из Киева в Запорожье.
Допустим, у него есть карта Украины, на которой указаны расстояния между каждой парой пересечений дорог. Как найти кратчайший маршрут? Один из возможных способов — пронумеровать все маршруты из Киева в Запорожье, просуммировать длины участков на каждом маршруте и выбрать кратчайший из них. Однако легко понять, что даже если исключить маршруты, содержащие циклы, получится очень много вариантов, большинство которых просто не имеет смысла рассматривать. Например, очевидно, что маршрут из Киева в Запорожье через Львов — далеко не лучший выбор. Точнее говоря, такой маршрут никуда не годится, потому что Львов находится относительно Киева совсем в другой стороне. В этой главе и в главе 25 будет показано, как эффективно решаются такие задачи.
В задаче о кратчайшем луши (злоггем-рагпз ргоЫеш) задается взвешенный ориентированный граф С = (У, Е) с весовой функцией ш: Е -> К, отображающей ребра на их веса, значения которых выражаются действительными числами. Вес (~че1йлг) пути р = (се, иы..., сь) равен суммарному весу входящих в него ребер: Часть Ч!. Алгоритмы для работы с графами Вес кратчайшего пути (з)зопез!-раба ~че(к(п) из вершины и в вершину п опреде- ляется соотношением п пп ~ю (р): и -+ о~ если имеется путь от и к и, р д(и,с) = 00 в противном случае. Тогда по определению крат чайигий путь (з!юпез! ра!)з) из вершины и в вершину о — это любой путь, вес которого удовлетворяет соотношению ю (р) = б (и, о).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
