(Начало

Иниииа/тизаидя переменных

Обновление ребра наи/еньшего веса из каждой невыбраннои Вершинин дыбранной

Отыскание ребра с наименыиим Весом от невыбранной вершины к Выбранной

Включение ребра В ОДМВ

Однако шаг 2 требует двух массивов CHOSEN и UNCHOSEN, чтобы найти минимальный вес ребра между вершиной в CHOSEN и вершиной в UNCHOSEN. Имея это в виду, мы можем представить себе реализацию шага 2 в виде проверки всех ребер с одной вершиной в

CHOSEN, а другой в UNCHOSEN. Как только будет найдено ребро с минимальным весом, невыбранная вершина этого ребра исключается из массива UNCHOSEN и добавляется к массиву CHOSEN. Шаг 2 можно затем повторить с обновленными массивами.

При более пристальном взгляде на этот подход к реализации шага 2 мы обнаруживаем, что будет производиться много лишних проверок ребер и что возникают некоторые трудности при обновлении массивов CHOSEN и UNCHOSEN. Более эффективная реализация шага 2 получается, если хранить только список невыбранных вершин UNCHSN(/), который первоначально содержит NUMUN=yM-1 вершин, и создать два дополнительных массива. Это будут массивы LIGHT, каждый /-Й элемент которого равен весу ребра между /-й вершиной и некоторой выбранной вершиной, и VERTEX, содержащий в /-М элементе выбранную вершину на этом ребре.

При наличии этих массивов шаг 2 можно реализовать следующим образом: (1) ищем ребро с наименьшим весом в массиве LIGHT; (2) исключаем /С-й элемент из списка UNCHSN (помещаем последнюю невыбранную вершину UNCHSN (NUMUN) в UNCHSN (/С)); (3) уменьшаем значение NUMUN, числа невыбранных вершин, на 1; (4) запоминаем или выдаем на печать вновь выбранное ребро LIGHT; (5) используя UNCHSN (/С) в качестве вновь выбранной вершины, обновляем значения LIGHT для остающихся невыбранных вершин, сравнивая LIGHT(/) с С(/, UNCHSN(/)).

Приняв решение о реализации самого трудного шага алгоритма PRIM, мы можем теперь завершить реализацию остальных шагов. Шаг О сводится к произвольному выбору вершины М в качестве начальной и к размещению вершин 1, 2, 3, . . . , М-1 в массиве UNCHSN. Шаг 1

Рис. 4.1.6. Более детальная блок-схема алгоритма PRIM.

реализуется посредством проверки, остались ли еще невыбранные вершины, т. е. не равно ли значение NUMUN нулю. Эти соображения сведены в блок-схему на рис. 4.1.6.

В программе на Фортране, показанной на рис. 4.1.7, мы произвольно решили отвести достаточное пространство в памяти для работы с сетью, имеющей 100 вершин. Символы в крайних правых позициях записи программы будут кратко пояснены; числа в левых позициях будут обсуждены в следующем разделе.

Оператор CALL"CHECK, на рис. 4.1.7 вызывает подпрограмму, которая должна проверять, допустимы ли значение М и значения С. Если обнаружено недопустимое значение, подпрограмма CHECK

SDBROUTINE PRIM(C,H,FROH,TO,COST.WEIGHT)

С ЭТА ПОДПРОГРАММА НАХОЛИТ ОСТОВНОЕ ДЕРЕВО НИНИМАГЬ-

С ного ВЕСА (ОЛНВ) ВО ВЗВЕШЕННОЙ СВПЗНОЙ СЕТИ G , ИС-

С ГОЛЬЗУЯ АЛГОРИТМ Р.ПРИМА (BELL SYSTEM TECH.J. 36

С (НОЯБРЬ 1957). 1389-1401). ДАННАЯ PEAflHSAUHR ЯВЛП-

С ЕТСЯ МОЯИ*ИКДиИЕЙ ПРОГРАММЫ В.КИВИНА И М.УИТНИ

С (СОММ.АСМ (АПРЕЛЬ 1972), АЛГОРИТМ 422). С

С ФОРМАЛЬНЫЕ ПАРАМЕТРЫ С

С C(I,J) ВЕС РЕБРА ,, СОЕДИНЯЮЩЕГО ВЕРШИНЫ I И J ,

С ГДЕ I.LE.C(1,J).LE.999999. ЕСЛИ fEbPO

С OTCYTCTBYET , ТО C(I,J) = 1 ООО ООО ,

ПРОИЗВОЛЬНОМУ БОЛЬШОМУ ЧИСЛУ.

с Н ВЕРШИНЫ в G ПРОНУМЕРОВАНЫ 1.....Н,

С ГДЕ 2.LE.M.LE.100

С FROM(I) 1-Е РЕБРО В ОДМВ СОЕДИНЯЕТ ВЕРШИНУ FROM(I)

Т0()- С ВЕРШИНОЙ Т0(1) ПРИ ЦЕНЕ COST(l)

С COST(I)

с WEIGHT ОБЩИЙ ВЕС ОДМВ

с ВНУТРЕННИЕ ПЕРЕМЕННЫЕ С

С EDGES ТЕКУЩЕЕ ЧИСЛО РЕБЕР В ОДМВ

С LIGHT(I) НАИМЕНЬШИЙ ВЕС РЕБРА ИЗ VERTEX(I) К

С UNCHSN(T)

С NEXT ОЧЕРЕДНАЯ ВЕРШИНА , ПРИСОЕДИНЯЕМАЯ К ОДМВ

с NUMUN ЧИСЛО НЕВЫБРАННЫХ ВЕРШИН

с UNCKSN(I) МАССИВ НЕВЫБРАННЫХ ВЕРШИН

с VERTEX(I) ВЕРШИНЫ ЧАСТИЧНОГО ОДМВ , БЛИЖАЙШИЕ К БЕР-

С ШИНЕ UNCHSN(I)

Рис. 4.1.7. Подпрограмма PRIM.

INTEGER EDGES .LIGHTdDD),NEXT,NUMUN,UNCK5K11D0) INTEGER VERTEXiIDD)

INTEGER C<1D0,10D),H,FR0M(1D0),10(1005.COSTllDO) INTEGER WEIGHT

= С ЛРОЕЕРКА ВХОДНЫХ ДАННЫХ НА ДОПУСТИМЫЕ ЗНАЧЕНИЯ = С

CALL СИЕСК1С.М)

= С ПРИСВОЕНИЕ НАЧАЛЬНЫХ ЗНАЧЕНИЙ (ИНИЦИАЛИЗАЦИЯ) = С " •

EOGES = D NEXT = Н NUMUN =. М-1 WE4GHT >» О 00 1 00 I I.NUHUN

UNC№.N(I) - I Н-1

LIGHT(I) = Cd.NEXTli М-1

VERTEX(I) . NEXT M-1

106 CONTINUE

С ОБНОВЛЕНИЕ ТАБЛИЦЫ РЕБЕР НАИМЕНЬШЕГО ВЕСА , СОЕДИНЯ-

С " ЮЩИХ КАВДУЮ НЕВЫБРАННУВ ВЕРШИНУ С КАКОЙ-НИБУДЬ ВЫБ-С РА НПО й

200 00 300 I = 1.I4UMUN м-1

J - UNC№N(I) М1М-1)/2

JK = C(J,NEXT) М(М-1)/2

IF(UIGHT(I) .LE. JK) GO TO 300 MlM-1)/2,»

VERTEX(I) - NEXT В

LIGHTllJ - JK E

300 CONTINUE HlM-D/a

ОТЫСКАНИЕ РЕБРА С НАИМЕНЬШИМ ВЕСОМ , СОЕДИНЯЮЩЕГО НЕВЫБРАННУЮ ВЕРШИНУ С ВЫБРАННОЙ

Рис. 4.1.7. Продолжение