6.13. Построение кратчайшего каркаса

Рассмотренная в п.5.12 модификация алгоритма дает "побочный продукт". В ней строится каркас графа и ее можно приспособить для получения кратчайшего каркаса, сумма ребер которого минимальна.

Создавая каркас, расширяем плотное окружение некоторого (любого) отправного узла. К множеству узлов каркаса всегда добавляем узел, связанный кратчайшим ребром с каким-либо из них. Если для каж­дого узла окружения хранить наименьшую длину ребра из ребер, ведущих в каркас, минимум ищется на множестве этих длин, кото­рых меньше n. Из этих длин и сформируем сортдерево. Ребро запо­минается как ссылка на узел каркаса, хранимая в массиве r. Если, например r[3] = 6, это означает ссылку 3-го узла на 6-й узел графа.

В принципе, разница, по сравнению с нахождением кратчайших пу­тей, лишь в одном: оценкой узла является длина ребра, соединяюще­го его и ближайший узел каркаса.

После каждого добавления узла в каркас приходится проверять реб­ра, идущие от узла вовне каркаса: некоторые смежные узлы впервые получат оценку (происходит расширение окружения), а оценка дру­гих - может измениться. Выявление "внешних" узлов просто: узел v, еще не вошедший в каркас, либо находится в сортдереве, либо для него элемент оглавления og[v] равен 0.

Пример 6.13.

Найдем кратчайший каркас для графа G2. До сих пор мы полагали веса ребер целыми. Чтобы допустить вещественные, в следующей программе определение tip = word, заменяйте определением tip = real (или укажите др. вещественный тип). В связи с этим массив описания графа составлен из записей; поле v - это номер вершины, поле d - вес инцидентного ей ребра. Из таких же записей построено сортдере­во de. Это внешние отличия; логика работы - та же, что и в блоке DeikDer (п.5.12). Строить каркас начнем от узла 1.

Constn=6; m=10; m1=2*m;

Type tip = word; zap = Record v:word; d:tip End;

sp = Array[1..m1] of zap; vec = Array[1..n+1] of word;

v1 = Array[1..n] of zap; mas = Array[1..n] of word;

Const opi:sp = ((v:2;d:20),(v:6;d:30),(v:4;d:30),(v:5;d:70), (v:1;d:20),(v:4;d:20),(v:5;d:100),(v:4;d:70), (v:5;d:40),(v:6;d:20),(v;1;d:30),(v:2;d:20), (v:3;d:70),(v:1;d:70),(v:2;d:100),(v:3;d:40), (v:6;d:30),(v:1;d:30),(v:3;d:20),(v:5;d:30));

stp: vec = (4,3,3,3,4,3,0); {Степени узлов графа G2 и ноль - в конце}

Var r: mas; j, L: word;

Procedure DeikKar (var opi:sp; stp:vec; var r:mas); Var de:v1; og:mas; g:tip; i,j,k,s,v,x:word;

Procedure Vniz (i: word); {Блокищетместодляновойоценки g узлаграф}

Begin If i > 1 Then {Сдвигом вправо кода позиции i узла сорт дерева}

Repeat j:= i Shr 1; {найдем позицию j его предшественника в дереве}

Lf g < de[j].d Then Begin de [i]:=de [j]; og [de[j].v]:=i; i:=j End Else j: = 1 {Закончено перемещение элементов дерева и освободилось}

Until j = 1; {место для оценки g вершины v; производим ее занесение}

De [i].d:= g; de [i].v:= v; og [v]:= i; r [v]:= L {Достраиваемкаркас r}

End {блока включения в сорт дерево оценки или уточнения ее места в нем}; Procedure Out; Label 1; {В Турбо Паскале 7.0 вместо Goto 1 можно}

Begin j:=1; k:=2; {использовать оператор Break, исключив метку}

While k<i do

Begin If de [k+1]. d < de[k].d Then k:= k+1;

If de [i].d <= de [k].d Then Goto 1;

De [j]:= de [k]; og [de[k].v]:=j; j:=k; k:= k+k End; 1: de [j]™ de [i]; og[de[i].v]:=j

End {блока исключения корневого элемен сортдерева};

Begin

s:=0; For j:= 1 to n do Begin s:= s + stpfj]; og[j]:=0 End;

If s <> m1 Then Writeln('Ошибка в описании или в значении m');

If s <> m1 Then Exit;

i:-1; de[1].v:=1; r[1]:=n+1; {Узел 1 графа сделаем корнем каркаса}

stp[n+1]:= s+1; {Строим оглавление для opi, заменяя степени ссылками}

For j:= n downto 1 do stp[j]:= stp[j+1] - stp[j];)

Repeat L:= de[1].v; Out; i:=i-1; og[L]:=n;

For k:= stp[L] to stp[L+1]-1 do Begin v:= opi[k].v; x:=og[v];

If x <= i Then Begin g:= opi[k].d;

If x = 0 Then Begin i:=i+1; Vniz(i) End

Else If g < de[x].d Then Vniz(x)

End

End

Until i = 0

End {блока DeikKar};

BEGIN DeikKar(opi, stp, r);

For j:=1 to n do write(r[j],' '); Readln

END.

Программа выведет следующее содержание r (массив каркаса):

О, 1, 6, 2, 6, 1,определяющее каркас

Узел 1 не ссылается на какой-либо другой, ибо был отправным, а на него ссылаются 2-й и 6-й узел и т. д.

Асимптотическая ВС - та же, что и при поиске кратчайших путей (см. п. 5.12).

Задание 5.13.

"Встречное" направление ссылок r_j (к корню) может оказаться неудобным для каких-либо применений. Запишите блок сложности О(n) для построения на основе массива г структуры с оглавлением, описывающей каркас.