![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Алгоритм Прима и поиск по приоритету
С точки зрения реализации алгоритм Прима, по-видимому, является простейшим из всех алгоритмов построения дерева MST, ему отдают предпочтение в случае насыщенных графов. Мы поддерживаем сечение графа, состоящее из древесных вершин (те, которые выбраны для представления дерева MST) и недревесных вершин (те, которые не попадают в дерево MST). Мы начинаем с того, что помещаем произвольную вершину в дерево MST, затем помещаем в MST минимальное пересекающее ребро (которое превращает недревесную вершину дерева MST в древесную) и повторяем подобную операцию V- 1 раз, пока все вершины не окажутся в дереве. Реализация алгоритма Прима " в лоб" следует непосредственно из этого описания. Чтобы найти очередное ребро для включения его в дерево MST мы должны исследовать все ребра, которые выходят из древесной вершины в недревесную вершину, затем выбрать Глава 20. Минимальные остовные деревья
Добавление вершины в дерево MST представляет собой инкрементное изменение: чтобы реализовать алгоритм Прима, мы внимательно исследуем природу такого инкрементного изменения. При этом главным образом мы заинтересованы в том, чтобы найти кратчайшее расстояние каждой недревесной вершины до дерева. Когда мы присоединяем вершину v к дереву, единственное изменение, касающееся недревесной вершины w, состоит в том, что с добавлением вершины v в дерево w становится ближе к этому дереву, нежели раньше. Короче говоря, нам не надо проверять расстояние от вершины w до каждой вершины дерева — нам нужно знать минимальное расстояние в каждый момент и проверять, вызывает ли добавление вершины v в дерево необходимость изменить это минимальное расстояние. Ориентированный чертеж возрастающего дерева MST показан справа от каждого чертежа графа. Ориентация есть побочный продукт изучаемого нами алгоритма: в общем случае само дерево MST мы рассматриваем как множество ребер, неупорядоченное и неориентированное. Для реализации этой идеи нам потребуются такие структуры данных, которые предоставляли бы следующую информацию: ■ Ребра дерева. ■ Самое короткое дерево, соединяющее недревесные вершины с деревом. ■ Длина этого ребра. Простейшей реализацией каждой из этих структур данных будет вектор, индексированный именами вершин (мы можем использовать этот вектор для хранения древесных ребер, индексируя их именами вершин по мере их добавления в дерево). Программа 20.6 представляет собой реализацию алгоритма Прима для насыщенных графов. Она использует для этих структур данных, соответственно, векторы mst, fir и wt. После включения нового ребра (и вершины) в дерево, мы должны выполнить еще две процедуры: ■ Проверить, приблизит ли добавление нового ребра какую-либо из недревесньх ■ Найти следующее ребро, подлежащее включению в искомое дерево. Реализация программы 20.6 решает обе эти задачи в течение одного просмотра недревесных вершин. Сначала она обновляет содержимое векторов wt[w] и fr[w], если v-w приближает w к дереву, после чего обновляется текущий минимум, если wt[w] (длина fr[w]) показывает, что w ближе к дереву, чем любая другая недревесная вершина с меньшим индексом). Свойство 20.6. Используя алгоритм Прима, можно найти дерево MST насыщенного графа за линейное время. Доказательство: Анализ программы 20.6 показывает, что время ее выполнения пропорционально V2 и поэтому линейно для случаев насыщенных графов. ■ Часть 5. Алгоритмы на графах
РИСУНОК 20.8. АЛГОРИТМ ПРИМА ПОСТРОЕНИЯ ДЕРЕВА MST Первое действие при вычислении дерева MST no алгоритму Прима предусматривает включение в это дерево вершины 0. Затем мы находим все ребра, которые соединяют 0 с другими вершинами (еще не включенными в это дерево), и выбираем из них самое короткое (слева вверху). Ребра, соединяющие древесные вершины с недревесными, заштрихованы (бахрома), их список приводится под каждым чертежом графа. Чтобы не усложнять чертеж, мы перечисляем ребра, образующие бахрому, в порядке возрастания их длины, так что самое короткое ребро в этом списке следует первым. В различных реализациях алгоритма Прима используются различные структуры данных для поддержания этого списка и определения минимального ребра. Второе действие заключается в переносе самого короткого ребра 0-2 (вместе с вершиной, в которую оно нас приводит) из бахромы в дерево (вторая диаграмма сверху слева). В-третьих, мы переносим ребро 0- 7 из бахромы в дерево и заменяем ребро 0-1 на 7-1, а ребро 0-6 на 7-6 в бахроме (поскольку с включением вершины 7 в дерево 1 и 6 становятся ближе к дереву), и включаем ребро 7-4 в бахрому (поскольку добавление вершины 7 в дерево превращает 7-4 в ребро, которое соединяет древесную вершину с недревесной) (третья диаграмма сверху слева). Далее, мы переносим ребро 7-1 в дерево (диаграмма слева внизу). В завершение вычислений мы исключаем ребра 7-6, 7-4, 4-3 и 3-5 из очереди, обновляем бахрому после каждой вставки с тем, чтобы зафиксировать обнаруженные более короткие или новые пути (диаграммы справа сверху вниз). Глава 20, Минимальные остовные деревья
РИСУНОК 20.9. АЛГОРИТМ ПРИМА, ОБЕСПЕЧИВАЮЩИЙ ПОСТРОЕНИЕ ДЕРЕВА MST Эта последовательность показывает, как растет дерево MST no мере того, как алгоритм Прима обнаруживает 1/4, 1/2, 3/4 всех ребер и все ребра дерева МST (сверху вниз). Ориентированное представление полного дерева MST показано справа.
|