Список переменных, используемых в качестве индексов, вместе с диапазонами их предполагаемых значений полезен при решении вопроса, не выходит ли индекс за предписанные пределы. В данном случае значения всех индексов заключены в пределах от 1 до М-1 или от 1 до NUMUN и числа М и NUMUN ограничены сверху числом 100 и снизу числом 0. Индекс не может принимать значение О благодаря двум последним операторам:

IF (NUMUN .NE. 0)GO TO 200 RETURN

Что касается вопроса о том, не зациклится ли подпрограмма, представляется, что это может произойти, если по какой-нибудь причине NUMUN никогда не обратится в нуль. Из приведенного выше списка видно, что, хотя NUMUN присутствует в шести операторах, ее значение изменяется только в двух:

NUMUN = М-1 (в начале программы)

NUMUN = NUMUN-1 (около конца программы)

Поскольку величина М объявлена как целая переменная, а подпрограмма CHECK определяет М как целую переменную со значениями между 2 и 100, мы можем быть в достаточной степени уверены, что программа не зациклится, так как значение NUMUN никогда не будет равно 0.

Что касается поиска чего-нибудь, что может привести к ошибке подпрограммы PRIM, можно задаться вопросом: могла бы подпрограмма когда-нибудь выбрать ребро с весом 1 ООО ООО? И если да, то что бы это значило?

Что касается проверки подпрограммы PRIM на конкретных данных, то рассмотрим: (1) сеть, у которой значения С(/, J) или М неправильные; (2) сеть с М=2 и M=lbO вершинами; (3) несколько маленьких сетей, для которых можно проверить ОДМВ вручную; (4) сеть со всеми равньми значениями С(/, J); (5) сеть, в которой С(/, /)< <С(/, J+1) для /=1, . . . , М-1 и /</. Чтобы проверить, что все операторы выполнялись, и для проверки эффективности реализации исследуем профиль исполнения подпрограммы PRIM.

Числа слева от операторов в программе на рис. 4.1.7 показывают, сколько раз выполняется каждый из них при вызове подпрограммы PRIM для отыскания ОДМВ в случайно сгенерированной сети с 50 вершинами. Использованная нами программа построения профилей не указывала количества выполнений операторов GOTO 300 и GOTO 400. Однако, зная, что Л+В=1225 и С--Ь=1225, мы можем вычислить, что они исполнялись соответственно 1225-151 = 1074 и 1225-122= = 1103 раз.

Этот профиль не только показывает, что каждый оператор был выполнен хотя бы однажды, но и подтверждает наш анализ сложности, проведенный в предыдущем разделе. Например, если M=50, то М{М-1)/2 =25(49)=1225. Этот профиль также показывает, что про-

грамма проводит основную часть своего времени, выполняя шесть операторов 1225 раз. Следовательно, именно на этих операторах нам следует сосредоточить внимание при попытках улучшить реализацию.

Внимательное изучение циклов DO 300 и DO 400 обнаруживает два места, в которых можно достичь экономии времени выполнения. Во-первых, не обязательно выполнять цикл DO 300 непосредственно после цикла DO 100. Можно было бы непосредственно после 100 CONTINUE вставить оператор GO ТО 350, где 350 - метка оператора, непосредственно следующего за 300 CONTINUE, т. е.

300 CONTINUE 350 К=1

Поскольку такое изменение подпрограммы PRIM устранило бы первое выполнение цикла DO 300-(М-1) операторов (ценой добавления одного оператора) - и так как оно не приводит к неоправданному усложнению логики, его стоит сделать. Во-вторых, цикл DO 400 (с необходимыми предосторожностями) можно было бы преобразовать.к виду DO 400 1=2, NUMUN. Это позволило бы избавиться от 1 = 1, так же как и от М-1 сравнений LIGHT (1) с самим собой, от М-1 выполнений оператора GO ТО 400 и от М-1 выполнений CONTINUE, т. е. не выполнялось бы 3 (М-1)+1 операторов. Однако при NUMUN= = 1 не следует выполнять этот цикл DO. Такого выполнения можно избежать, заменив в конце программы строки

ГР (NUMUN .NE. 0) GO TO 200

RETURN

следующими операторами:

IF (NUMUN .GE 2) GO TO 200

J = UNCHSN(1)

JK=C(J, NEXT) IF (UGHT(1) .LE. JK) GO TO 500

VERTEX(1) = NEXT

LIGHT(1)=JK SOO EDGES=EDGES+1 FROM(EDGES)=J T0(EDGES)=VERTEX(1) C0ST(EDGES) = LIGHT(1) WEIGHT = WE1GHT+UGHT(1) RCTURN END

Можно считать, что эти новые операторы в свою очередь позволяют избежать выполнения 16 операторов, с риском, что слржность логики достигнет предела, за которым могла бы возникнуть ошибка.

Таким образом, общая экономия в результате этих изменений составит 5(М-l)~l-f3(M-1)+Ц-16=8М+8 операторов. По сравнению с верхней границей 5-1-15М-14 числа выполнений операторов в подпрограмме PRIM экономия 8М+8 операторов составит при-

близительно 14% для M=10, 6% для М=25, 3% для М=50 и 1% для М = 100.

На рис. 4.2.1 дан пересмотренный вариант подпрограммы PRIM с учетом сделанных замечаний. Кратности выполнения операторов для той же случайной сети, что и на рис. 4.1.7, дают экономию 3% по сравнению с первоначальным вариантом. Однако это улучшение не следует рассматривать слишком серьезно, так как оно не обязательно приводит к такому же проценту уменьшения времени выполнения. Действительная экономия времени при выполнении зависит от конкретного компилятора и степени оптимизации.

SUBROUTINE FRlH(C,H,FFCM,TO,C0ET,WErGHT)

с эта годпрогранма находит остовное дерево нининадь»

С ного БЕСА (одмв) во взвешенной связной сети g . ис-

С годьзуя адг0р*1тм р.прима (BELU SYSTEM TECH.J. 36

с (ноябрь 1957), 1339-1401). данная реализация явля-

с ется-модификацией программы в.кивина и М.УИТНИ

С (сомн.асм (апрель 1972), АЛГи,>итм 422). i С

с й« ФОРМАЛЬНЫЕ параметры С

с Cd.J) бес ребра , соединявшего вершины Г И J ,

С где ).LE.C(I,J).LE;999999. если ребро

С отсутствует , то C(I,J) =. 1 оос ссо .

С произвольному большому числу.

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

с ГДЕ 2.le.m.ue.100

с FMMd) J-epEEPO б одмв соединяет вершину FROHtl)

С т0(1) С вершиной т0{1) при цене COSKU

С СОЗТ(Г)

с weight ОБЩИЙ SEC ОДМВ

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

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

С LIGKTdJ НАИМЕНЬШИЙ БЕС ре6ра ИЗ VERTEXd) К

С UNC)eN(l)

С «ЕХТ ОЧЕРЕДНАЯ ВЕРШИНА , 11РИС0ЕАИНЯЕ{1АП К ОДНВ

с шин число НЕБЙРАННЫХ ВЕРШИВ

с UNCKNlIl ПАССИВ НЕВЫБРАННЫХ ЕЕРШИ»

с VIRTEXtlJ ВЕРШИНЫ ЧАСТИЧНОГО ОДНВ , ЕЛИЙМЙШИЕ К ЕЕР-

С ШИНЕ UNCHSNd) .

Рис. 4.2.1. Подпрограмма PRIM после внесения изменений.