Mark[i]:=i; k:=0;t:=M;
Mark[i]:=i;
k:=0;t:=M;
while k<N-1 do begin i:=1;
while (i<=t) and (Mark[P[1,i]]=Mark[P[2,i]]) and (P[1,i]<>0) do Inc(i);
Inc(k);
<вывод или запоминание ребра каркаса>;
Change_Mark(Mark[P[1,i]],Mark[P[2,i]]);
end;
end;
3.3.4. Каркас минимального веса. Метод Прима
Дано. Связный неориентированный граф G=<V,E>. Ребра имеют вес. Граф описывается матрицей смежности A (array[1..N,1..N] of integer). Элемент матрицы, не равный нулю, определяет вес ребра. Результат. Каркас с минимальным суммарным весом Q=<V,T>, где T?E.
Отличие от метода Краскала заключается в том, что на каждом шаге строится дерево, а не ациклический граф. Для реализации метода необходимы две величины множественного типа SM и SP (set of 1..N). Первоначально значением SM являются все вершины графа, а SP пусто. Если ребро <i,j> включается в T, то номера вершин i и j исключаются из SM и добавляются в SP.
Пример. Граф и его каркас.
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
