Означення 1. Запровадимо такі поняття:
Підграф G'(V',E') графа G(V,E) називають остовним (каркасним), якщо V' = V, тобто множини вершин графа G і підграфа G' збігаються.
Остовним (каркасним) деревом графа називають його довільний остовний (каркасний) підграф, що є деревом.
Мінімальним остовним деревом зваженого графа називають таке каркасне дерево графа, що сума ваг його ребер не перевищує таку суму ваг його ребер довільного іншого остовного дерева.
Ідея першого методу пошуку мінімального каркасного дерева полягає у долученні ребра з мінімальною вагою до певної множини E (не обов'язково дерева) без утворення циклів.
Алгоритм Крускала
(Krushkal's algorithm)
Надамо множині E значення величини ∅ — порожньої множини.
Визначимо, які з ребер початкового графа, що не належать до E, при долученні до E не утворюють циклів.
Якщо такі ребра є, то:
серед цих ребер визначимо «найлегше», тобто з найменшою вагою;
долучимо це ребро до множини E;
переходимо до виконання пункту 2.
Якщо таких ребер немає, то припиняємо побудову мінімального остовного дерева.
Теорема 1. Алгоритм Крускала створює мінімальне каркасне дерево.
Доведення (від супротивного). Позначимо через
e1, e2, e3, …, en ребра дерева T у тому порядку, як їх вибирають згідно з алгоритмом Крускала. Нехай k — найбільше таке натуральне число, при якому e1, e2, e3, …, ek — ребра деякого мінімального остовного дерева T'. Припустимо, що k < n. Приєднаємо ребро ek + 1 до мінімального остовного дерева T'. Утворений граф містить цикл. Побудуємо дерево T'', видаливши з цього циклу деяке ребро e, відмінне від e1, e2, …, ek, ek + 1. Таке ребро існує, бо інакше маємо суперечність з означенням k. Вага e не менша за вагу ek + 1, бо інакше:
або алгоритм Крускала вибирає e перед ek + 1;
або ребра e1, e2, ... , ek, e, що є ребрами дерева T', утворюють цикл.
Отже, дерево T'' утворено з мінімального каркасного дерева T' заміною ребра e на ребро ek+1 без збільшення ваги дерева. Тому T'' — мінімальне остовне дерево, що містить ребра
e1, e2, …, ek, ek + 1. Останнє суперечить означенню k. Таким чином, k = n, а T — мінімальне каркасне дерево.
Ідея наступного методу пошуку мінімального каркасного дерева полягає у долученні ребра до дерева зі збереженням структури дерева (зв'язність та відсутність циклів).
Алгоритм Пріма
(Prim's algorithm)
Утворимо дерево T1 з одним ребром:
виберемо довільну вершину v0 початкового графа G;
виберемо ребро e1 з найменшою вагою серед тих, що мають вершину v0;
Якщо існують вершини початкового графа G зовні останнього побудованого дерева Tk з ребрами e1, e2, e3, …, ek, то робимо таке:
вибираємо ребро ek + 1 з найменшою вагою серед тих, у яких одна вершина належить до Tk, а інша вершина не належить;
утворюємо дерево Tk + 1 долученням до Tk вибраного ребра ek + 1 і його вершин;
збільшуємо величину k на 1;
переходимо на початок виконання пункту 2.
Якщо всі вершини початкового графа G належать до дерева Tk, то припиняємо побудову мінімального остовного дерева.
Теорема 2. Алгоритм Пріма створює мінімальне каркасне дерево.
Доведення (від супротивного) аналогічне доведенню попередньої теореми про коректність алгоритму Крускала.
Позначимо через
e1, e2, e3, …, en ребра дерева Tn у тому порядку, як їх вибирають згідно з алгоритмом Пріма. Нехай k — найбільше таке натуральне число, при якому
e1, e2, e3, …, ek — ребра деякого мінімального остовного дерева T'. Припустимо, що k < n. Приєднаємо ребро ek + 1 до мінімального остовного дерева T'. В утвореному таким чином графі є цикл. Цикл містить ребро e, відмінне від ek + 1, що також має лише одну вершину в дереві Tk. Утворимо дерево T'', вилучивши з T' ребро e і долучивши ребро ek + 1. Згідно з алгоритмом Пріма, вага ek + 1 не перевищує вагу e, тому T'' є мінімальним каркасним деревом, що суперечить означенню k. Отже,
k = n, Tn — мінімальне каркасне дерево.
Алгоритм Пріма (матричне подання)
Утворимо W — квадратну матрицю, що має n рядків і стовпчиків, де n — кількість вершин даного графа, таким чином: для j і k в межах від 1 до n включно W(j, k) дорівнює вазі ребра з вершинами vj і vk, якщо таке існує, і дорівнює 0, якщо такого ребра не має.
Матрицю W* утворимо з W доповненням одного рядка і стовпчика. У перший рядку в останньому стовпчику матриці W* розташуємо символ *. У першиму стовпчику всі елементи замінимо на 0, а в останньому рядку першого стовпчика розташуємо символ U.
Виберемо найменше число серед натуральних елементів матриці W*, при якому:
i-ий рядок W*, що містить вибраний елемент, містить * у (n + 1)-му стовпчику;
j-ий стовпчик W*, що містить вибраний елемент, не містить U у (n + 1)-му рядку.
Перетворимо матрицю W* таким чином:
розташуємо символ * в останньому (n + 1)-му стовпчику j-го рядка;
замінимо на 0 решту чисел j-го рядка;
розташуємо символ U в останньому (n + 1)-му рядку j-го стовпчика.
Долучаємо ребро (vi; vk) до остовного дерева.
Кроки 3–5 виконуємо доти, поки є можливість вибору.
Подамо приклад програми мовою Turbo Pascal 7.0 з коментарями щодо структури вхідних і вихідних даних.
{$I+}{$N+} {Верхнi межi кiлькостi:}
const nv_max=2000; {вершин}
ne_max=4000; {ребер}
type wordv=array[0..ne_max] of word;
longe=array[0..ne_max] of longint;
used=array[1..nv_max] of boolean;
var w: ^longe; {Ваги ребер}
a,b: ^wordv; {Вершини ребер}
u: ^used;{Наявнiсть вершини у деревi}
nv, {Кiлькiсть вершин}
ne, {Кiлькiсть ребер}
nt, {Кiлькiсть вершин дерева}
k: word; o: text;
procedure let (j,k: word); BEGIN
a^[j]:=a^[k];
b^[j]:=b^[k];
w^[j]:=w^[k] END;
procedure swap(j,k: word); BEGIN
let(0,j);
let(j,k);
let(k,0) END;
{Швидке впорядкування}
procedure quick (left,right: word);
var l,r: word; BEGIN
swap(left,left+random(right-left+1));
l:=left;
r:=right;
let(0,l);
repeat
while (w^[r] >= w^[0]) and (l < r) do dec(r);
let(l,r); let(r,0);
while (w^[l] <= w^[0]) and (l < r) do inc(l);
let(r,l); let(l,0);
until l=r; let(l,0);
if left < l-1 then quick(left,l-1);
if l+1 < right then quick(l+1,right) END;
BEGIN
nv:=0; ne:=0; new(a); new(b); new(w);
assign(o,'PRIM.DAT'); reset(o);
{Зчитування рядкiв вхiдного файлу, кожний
з яких мiстить номери вершин i вагу ребра}
repeat inc(ne);
readln(o,a^[ne],b^[ne],w^[ne]);
if a^[ne] > nv then nv:=a^[ne];
if b^[ne] > nv then nv:=b^[ne];
until seekeof(o); close(o);
randomize; quick(1,ne); new(u);
for k:=1 to nv do u^[k]:=false;
{Створення мiнiмального дерева й
запис його ребер у вихiдний файл}
assign(o,'PRIM.RES'); rewrite(o);
writeln(o,a^[1],' ',b^[1],' ',w^[1]);
u^[a^[1]]:=true;
u^[b^[1]]:=true;
nt:=2;
repeat k:=1;
repeat inc(k)
until (u^[a^[k]] and (not u^[b^[k]])) or
(u^[b^[k]] and (not u^[a^[k]]));
inc(nt);
writeln(o,a^[k],' ',b^[k],' ',w^[k]);
u^[a^[k]]:=true;
u^[b^[k]]:=true;
until nt=nv; close(o); dispose(u);
dispose(a); dispose(b); dispose(w) END.