пает массив С размера п х п, чьи элементы C[i, j] равны стоимости ребер (i, ;). Если ребра не существуют, то элемент C[i,j] полатается равным некоторому достаточно большому числу.

После нахождения очередной верщины к остовного дерева LOWCOST[k\Iloжvcя равным infinity (бесконечность), очень большому числу, такому, чтобы эта вершина уже в дальнейшем не рассматривалась. Значение числа infiinity должно быть больше стоимости любого ребра графа.

© ©

Рис. 7.6. Последовательность построения остовного дерева алгоритмом Прима

Листинг 7.2. Программа выполнения алгоритма Прима

procedure Prim ( С: аггау[1..п, 1..п] of real ) ,-

{ Prim печатает ребра остовного дерева минималвной стоимости для графа с вершинами {1, . .., п) и матрицей стоимости С)

LOWCOST: array[1..п] of real; CLOSEST: array[1. .л] of integer;

i, j, kr min: integer;

{ i и j - индексы. При просмотре массива LOWCOST

к - номер найденной вершины, rain = LOWCOST[k] }

(2) (3)

begin

for i:= 2 to п do begin

{ первоначалвно в множестве О толвко вершина 1 ) LOlfCOSTli] := С[1, i] ; CLOSESTiH-. =1

end;

(4) for i;- 2 to п do begin

{ поиск вне множества U наилучшей вершины к, имеющей инцидентное ребро, оканчивающееся в множестве О }

(5) mln:= L0MC0ST[2] ;

(6) к: = 2;

(7) for j: = 3 to n do

(8) if LOMCOSTlj] < min then begin

(9) min: = LOWCOSTlj] ;

(10) k:=j

end;

(11) writelnik, CLOSESTlk]) ; { вывод ребра на печать }

(12) LOWCOST[k] := Infinity; { к добавляется в множество U }

(13) for J:= 2 to л do { корректировка стоимостей в U }

(14) if (С[к, j] < LOWCOST[j]) and

{LCmcOST[j] < infinity) then begin

(15) LOWCOSTlj] := C[k, j] i

(16) CLOSEST].j\ := к end

end; { Prim }

Время выполнения алгоритма Прима имеет порядок О(л), поскольку выполняется п - 1 итерация внешнего цикла строк (4) - (16), а каждая итерация этого цикла требует времени порядка 0(п) для выполнения внутренних циклов в строках (7) - (10) и (13) - (16). Если значение га достаточно большое, то использование этого алгоритма не рационально. Далее мы рассмотрим алгоритм Крускала нахождения остовного дерева минимальной стоимости, который выполняется за время порядка 0(е logs), где е - количество ребер в данном графе. Если е значительно меньше иг, то алгоритм Крускала предпочтительнее, но если е близко к п, рекомендуется применять алгоритм Прима.

Алгоритм Крускала

Снова предположим, что есть связный граф G = (V, Е) с множеством вершин У={1, 2, п) и функцией стоимости с, определенной на множестве ребер Е. В алгоритме Крускала (Kruskal) построение остовного дерева минимальной стоимости для графа G начинается с графа Т = (V, 0), состояшего только из га вершин графа G и не имеюшего ребер. Таким образом, каждая вершина является связной (с самой собой) компонентой. В процессе выполнения алгоритма мы имеем набор связных компонент, постепенно объединяя которые формируем остовное дерево.

При построении связных, постепенно возрастаюших компонент поочередно проверяются ребра из множества Е в порядке возрастания их стоимости. Если очередное ребро связывает две вершины из разных компонент, тогда оно добавляется в граф Т. Если это ребро связывает две вершины из одной компоненты, то оно отбрасывается, так как его добавление в связную компоненту, являющуюся свободным деревом, приведет к образованию цикла. Когда все вершины графа G будут принадлежать одной компоненте, построение остовного дерева минимальной стоимости Т для этого графа заканчивается.

Пример 7.5. Рассмотрим помеченный граф, представленный на рис. 7.4,а. Последовательность добавления ребер в формирующееся дерево Т показана на рис. 7.7. Ребра стоимостью 1, 2, 3 и 4 рассмотрены первыми и все включены в Т, поскольку их добавление не приводит к циклам. Ребра (1, 4) и (3, 4) стоимостью 5 нельзя включить в Т, так как они соединяют вершины одной и той же компоненты (рис. 7.7,г) и поэтому замыкают цикл. Но оставшееся ребро (2, 3) также стоимостью 5 не создает цикл. После включения этого ребра в Т формирование остовного дерева завершается. D

©

©

© ©

©

©

Рис. 7.7. Последовательное формирование остовного дерева минимальной стоимости посредством алгоритма Крускала

Этот алгоритм можно реализовать, основываясь на множествах (для вершин и ребер) и операторах, рассмотренных в главах 4 и 5. Прежде всего, необходимо множество ребер Е, к которому можно было бы последовательно применять оператор DELETEMIN для отбора ребер в порядке возрастания их стоимости. Поэтому множество ребер целесообразно представить в виде очереди с приоритетами и использовать для нее частично упорядоченное дерево в качестве структуры данных.

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

\. Оператор MERGE(A, В, С) объединяет компоненты 4 и 5 из набора С и результат объединения помешает или в А, или в S.

2, Функция FIND(ii, С) возврашает имя той компоненты из набора С, которая содержит вершину V.

3. Оператор INITIAL(A, v. С) создает в наборе С новую компоненту с именем 4, со-держашую только одну вершину v.

Напомним, что в разделе 5.5 для множеств, поддерживаюших операторы MERGE и FIND, мы ввели абстрактный тип данных, который назвали MFSET. В. эскизе программы (листинг 7.3), реализуюшей алгоритм Крускала, используется этот тип данных.

Отметим, что операторы MERGE и FIND здесь несколько отличаются от одноименных операторов из раздела 5,5, поскольку сейчас С - параметр, указывающий, где находятся множества А к В.