Алгоритм Прима и поиск по приоритету

С точки зрения реализации алгоритм Прима, по-видимому, является простейшим из всех алгоритмов построения дерева MST, ему отдают предпочтение в случае насыщенных графов. Мы поддерживаем сечение графа, состоящее из древесных вершин (те, которые выбраны для представления дерева MST) и недревесных вершин (те, которые не попада­ют в дерево MST). Мы начинаем с того, что помещаем произвольную вершину в дерево MST, затем помещаем в MST минимальное пересекающее ребро (которое превращает недревесную вершину дерева MST в древесную) и повторяем подобную операцию V- 1 раз, пока все вершины не окажутся в дереве.

Реализация алгоритма Прима " в лоб" следует непосредственно из этого описания. Что­бы найти очередное ребро для включения его в дерево MST мы должны исследовать все ребра, которые выходят из древесной вершины в недревесную вершину, затем выбрать

Глава 20. Минимальные остовные деревья

из них самое короткое и поместить его в дерево MST. Мы здесь не будем рассматривать соответствующую программную реализацию по причине ее исключительно высокой сто­имости (см. упражнения 20.35—20.37). Применение простых структур данных, позволяю­щих устранить повторные вычисления, приводят упрощению алгоритма и повышению его быстродействия.

Добавление вершины в дерево 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 показывает, что время ее выполнения пропор­ционально V² и поэтому линейно для случаев насыщенных графов. ■

Часть 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 показано справа.