Міністерство освіти і науки України
Сумський державний університет
Кафедра Інформатики
Курсова робота
з дисципліни
"Теорія алгоритмів і математична логіка"
на тему:
"Алгоритми пошуку кістяка Прима та Крускала"
Суми 2006
Зміст
Завдання
Вступ
Теоретична частина
Практична реалізація
Висновок
Програмний код
Література
Завдання
Розробити програмну реалізацію рішення задачі про мінімальний покриває дереві (побудова мінімального кістяка). Для знаходження мінімального покривного дерева використовувати алгоритми Прима і Крускала.
Вихідна інформація про ребрах графа знаходиться в текстовому файлі dan. Txt.
Вступ
Нехай є зв'язний неорієнтований граф G = (V, Е), в якому V - безліч контактів, а E - безліч їх можливих попарних сполук. Для кожного ребра графа (u, v) задано вага w (u, v) (довжина дроту, необхідного для з'єднання u і v). Завдання полягає в знаходженні підмножини Т Е, що зв'язує усі вершини, для якого сумарна вага мінімальний.
w (T) = w (u, v)
Таке підмножина Т буде деревом (оскільки не має циклів: в будь-якому циклі один з дротів можна видалити, не порушуючи зв'язності). Зв'язний підграф графа G, що є деревом і що містить всі його вершини, називають покриває деревом цього графа. (Іноді використовують термін "кістяк"; для стислості ми будемо говорити просто "кістяк".)
Далі ми розглянемо задачу про мінімальний покриває дереві. (Тут слово "мінімальне" означає "має мінімально можливий вагу".)
Рис 1
На Рис 1 показано на прикладі мінімальне покриває дерево. На кожному ребрі графа вказана вага. Виділено ребра мінімального покриває дерева (сумарна вага 37). Таке дерево не єдино: замінюючи ребро (Ь, с) ребром (а, h), отримуємо інше дерево того ж ваги 37.
Ми розглянемо два способи вирішення завдання про мінімальний покриває дереві: алгоритми Крускала і Прима. Кожен з них легко реалізувати з часом роботи O (E logV), використовуючи звичайні виконавчі купи. Застосувавши фібоначчійовий купи, можна скоротити час роботи алгоритму Прима до O (E + V logV) (що менше Е logV, якщо | V | багато менше \ Е \).
Обидва алгоритми слідують "жадібної" стратегії: на кожному кроці вибирається "локально найкращий" варіант. Не для всіх завдань такий вибір приведе до оптимального рішення, але для задачі про покриває дереві це так. Тут буде описана загальна схема алгоритму побудови мінімального кістяка (додавання ребер одного за одним). Надалі будуть вказані дві конкретних реалізації загальної схеми.
Отже, нехай дано зв'язний неорієнтований граф G = (V, E) і вагова функція w: Е . Ми хочемо знайти мінімальне покриває дерево (остов), слідуючи жадібної стратегії.
Загальна схема всіх наших алгоритмів буде така. Бажаємий остов будується поступово: спочатку до порожньому безлічі А на кожному кроці додається одне ребро. Безліч А завжди є підмножиною деякого мінімального кістяка. Ребро (u, v), що додається на черговому кроці, вибирається так, щоб не порушити цієї властивості: А {(U, v)} теж повинно бути підмножиною мінімального кістяка. Ми називаємо таке ребро безпечним ребром для А.
Generic - MST (G, w)
1 А
2 while A не є кістяком
3 do знайти безпечне ребро (u, v) для А
4 А A
{(U, v)}
5 return A
Рис. 2. Два зображення одного і того ж розрізу графа з Рис 1.
(А) Вершини безлічі S зображені чорними, його доповнення V \ S - білим. Ребра, що перетинають розріз, з'єднують білі вершини з чорними. Єдине легке ребро, що перетинає розріз - ребро (d, с). Безліч А складається з сірих ребер. Розріз (s, V \ S) погоджений з А (ні одне ребро з А не перетинає розріз).
(Ь) Вершини безлічі S зображені ліворуч, вершини V \ S - справа. Ребро перетинає розріз, якщо воно перетинає вертикальну пряму.
За визначенням безпечного ребра властивість "А є підмножиною деякого мінімального кістяка" (для порожньої множини це властивість, очевидно, виконано) залишається істинним для будь-якого числа ітерацій циклу, так що в рядку 5 алгоритм видає мінімальний кістяк. Звичайно, головне питання в тому, як шукати безпечне ребро у рядку 3. Таке ребро існує (якщо А є підмножиною мінімального кістяка, то будь-яке ребро цього остова, що не входить в А, є безпечним). Зауважимо, що безліч А не може містити циклів (оскільки є частиною мінімального кістяка). Тому що додається в рядку 4 ребро з'єднує різні компоненти графа G a = (V, A), і з кожною итерацией циклу число компонент зменшується на 1. Спочатку кожна точка являє собою окрему компоненту; в кінці весь кістяк - одна компонента, так що цикл повторюється | V | - 1 раз.
Теоретична частина
Алгоритм Крускала
У будь-який момент роботи алгоритму Крускала безліч А вибраних ребер (частина майбутнього остова) не містить циклів. Воно з'єднує вершини графа в кілька зв'язкових компонент, кожна з яких є деревом. Серед всіх ребер, що з'єднують вершини з різних компонент, береться ребро найменшої ваги. Треба перевірити, що воно є безпечним.
Нехай (u, v) - таке ребро, що з'єднує вершини з компонент З 1 і C 2 - Це ребро є легким ребром для розрізу (С 1, V \ C 1).
Реалізація алгоритму Крускала використовує структури даних для непересічних множин. Елементами множин є вершини графа. Нагадаємо, що Find - Set (u) повертає представника безлічі, що містить елемент u. Дві вершини u і v належать одному безлічі (компоненті), якщо Find - Set (u) = Find - Set (v). Об'єднання дерев виконується процедурою Union. (Строго кажучи, процедурам Find - Set і Union повинні передаватися покажчики на u і v)
MST-Kruskal (G, w)
1 A
2 for кожної вершини v V [G]
3 do Make - Set (v)
4 порядок ребра Е за вагами
5 for (u, v) E (у порядку зростання ваги)
6 do if Find-Set (u) Find-Set (v)
7 then A: = A {(U, v)}
8 Union (u, v)
9 return A
Спочатку (рядки 1-3) безліч А порожньо, і є | V | дерев, кожне з яких містить по одній вершині. У рядку 4 ребра з Е упорядковуються по неспадання ваги. У циклі (рядки 5-8) ми перевіряємо, чи лежать кінці ребра в одному дереві. Якщо так, то ребро не можна додати до лісу (не створюючи циклу), і воно відкидається. Якщо ні, то ребро додається до А (рядок 7), і два з'єднаних їм дерева об'єднуються в одне (рядок 8).
Підрахуємо час роботи алгоритму Крускала. Будемо вважати, що для зберігання непересічних множин використовується метод з об'єднанням за рангом і стиском шляхів - найшвидший з відомих. Ініціалізація займає час O (V), упорядкування ребер у рядку 4 - O (E logE). Далі виробляється O (Е) операцій, в сукупності займають час О (Е (Е, V)). (Основний час йде на сортування).
Алгоритм Прима
Як і алгоритм Крускала, алгоритм Прима відповідає загальній схемі алгоритму побудови мінімального кістяка. У цьому алгоритмі зростаюча частина кістяка представляє собою дерево (безліч ребер якого є А). Формування дерева починається з довільною кореневої вершини r. На кожному кроці додається ребро найменшої ваги серед ребер з'єднують вершини цього дерева з вершинами не з дерева. За слідству такі ребра є безпечними для А, так що в результаті виходить мінімальний кістяк.
При реалізації важливо швидко вибирати легке ребро. Алгоритм отримує на вхід зв'язний граф G і корінь r мінімального покриває дерева. У ході алгоритму всі вершини, ще не потрапили в дерево, зберігаються в черзі з пріоритетами. Пріоритет вершини v визначається значенням key [u], що дорівнює мінімальній вазі ребер, що з'єднують v з вершинами дерева А. (Якщо таких ребер немає, вважаємо key [V] = ). Поле
[V] для вершин дерева вказує на батька, а для вершини v
Q вказує на вершину дерева, в яку ведуть ребро ваги key [v] (одне з таких ребер, якщо їх декілька). Ми не зберігаємо безліч А вершин строімого дерева явно; його можна відновити як
A = {(v, [V]): v
V \ {r} \ Q}.
У кінець роботи алгоритму чергу Q порожня, і безліч
A = {(v, [V]): v
V \ {r}}.
є безліч ребер покриває дерева.
MST-Prim (G, W, r)
1 Q V [G]
2 for для кожної вершини u Q
3 do key [u]
4 key [r] 0
5 [R]
nil
6 while Q
7do u Extract-Min (Q)
8 for для кожної вершини v Adj [u]
9 do if v Q і w (u, v) <key [v]
10 then [V]
u
11 key (v) w (u, v)
Після виконання рядків 1-5 і першого проходу циклу в рядках 6 листопада дерево складається з єдиної вершини r, всі інші вершини знаходяться в черзі, і значення key [v] для них дорівнює довжині ребра з r в v або , Якщо такого ребра немає (у першому випадку
[V] = r). Таким чином, виконаний описаний вище інваріант (дерево є частина деякого кістяка, для вершин дерева полі
вказує на батька, а для інших вершин на "найближчу" вершину дерева - вага ребра до неї зберігається в key [v].
Час роботи алгоритму Прима залежить від того, як реалізована чергу Q. Якщо використовувати двійкову купу (7), ініціалізацію в рядках 1-4 можна виконати за допомогою процедури Build - Heap за час O (V). Далі цикл виконується \ V \ раз, і кожна операція Extract - Min займає час O (logV), всього O (V logV). Цикл for у рядках 8-11 виконується в загальній складності О (Е) раз, оскільки сума ступенів вершин графа дорівнює 2 \ Е \. Перевірку приналежності в рядку 9 всередині циклу for можна реалізувати за час O (1), якщо зберігати стан черзі ще і як бітовий вектор розміру | V |. Присвоєння в рядку 11 має на увазі виконання операції зменшення ключа (Decrease - Key), яка для двійкової купи може бути виконана за час O (logV). Таким чином, всього отримуємо O (V logV + E logV) = O (E logV) - та ж сама оцінка, що була для алгоритму Крускала.
Однак ця оцінка може бути покращена, якщо використовувати в алгоритмі Прима фібоначчійовий купи, за допомогою неї можна виконувати операцію Extract - Min за облікове час O (logV), а операцію Decrease - Key - за (облікове) час O (1). (Нас цікавить саме сумарний час виконання послідовності операцій, так що амортизований аналіз тут в самий раз.) Тому при використанні фібоначчійовий куп для реалізації черзі час роботи алгоритму Прима складе O (Е + V logV).
Програмна реалізація
Реалізуємо вищеописані алгоритми на практиці з допомогою Delphi 7.
Даний скрін є підтвердженням виконаної роботи.
Висновок
Порівнювати будемо за кількістю витраченого часу пошуку дерева, за сумарним вазі дерева, за кількістю порівнянь та присвоєнь для кожного з алгоритмів. Час обчислюється як середній час виконання алгоритмів.
Для алгоритму Прима кількість порівнянь і присвоювання більше, так як потрібно сортувати дані два рази (в алгоритмі Крускала 1 раз).
Можна зробити висновок, що для знаходження кістяка для графів з великою кількістю вершин, алгоритм Прима буде витрачати більше часу. Також для розріджених графів більш применителей алгоритм Крускала.
Програмний код
program Project1;
uses
Forms,
Unit1 in 'Unit1.pas' {Main},
Unit2 in 'Unit2.pas' {AboutBox};
{$ R *. res}
begin
Application.Initialize;
Application.CreateForm (TMain, Main);
Application.CreateForm (TAboutBox, AboutBox);
Application.Run;
end.
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Unit2, Menus;
type
TRebro = record
Fst, Lst, Vs: byte;
end;
Gr = array [1 .. 256] of TRebro;
TVect = array [1 .. 256] of byte;
TMain = class (TForm)
Label1: TLabel;
Label2: TLabel;
Button2: TButton;
Label3: TLabel;
Label4: TLabel;
Button3: TButton;
Label5: TLabel;
Label6: TLabel;
Label7: TLabel;
Label8: TLabel;
Label9: TLabel;
Label10: TLabel;
Label11: TLabel;
Label12: TLabel;
Label13: TLabel;
Label14: TLabel;
Label15: TLabel;
Label16: TLabel;
Label17: TLabel;
MainMenu1: TMainMenu;
N1: TMenuItem;
N2: TMenuItem;
N3: TMenuItem;
N4: TMenuItem;
Label18: TLabel;
Label19: TLabel;
procedure FormCreate (Sender: TObject);
procedure Button2Click (Sender: TObject);
procedure Button3Click (Sender: TObject);
procedure N2Click (Sender: TObject);
procedure N4Click (Sender: TObject);
private
{Private declarations}
public
{Public declarations}
end;
var
Main: TMain;
X: GR;
Mark: TVect;
R, V: byte; / / кількість ребер і вершин відповідно
procedure LoadGraph;
implementation
{$ R *. dfm}
Function Timer: longint;
const c60: longint = 60;
var h, m, s, s100: word;
begin
decodetime (now, h, m, s, s100);
timer: = ((h * c60 + m) * c60 + s) * 100 + s100;
end;
procedure LoadGraph;
var f: textfile;
i: byte;
begin
i: = 1;
Assignfile (f, 'dan.txt');
Reset (f);
R: = 0;
V: = 0;
Readln (f, R, V);
while not eof (f) do
begin
Readln (f, X [i]. Fst, X [i]. Lst, X [i]. Vs);
Main.Label2.Caption: = Main.Label2.Caption + IntToStr (X [i]. Fst) + '' + IntToStr (X [i]. Lst) +
'' + IntToStr (X [i]. Vs) + # 13;
inc (i);
end;
end;
procedure TMain.FormCreate (Sender: TObject);
begin
LoadGraph;
end;
/ / Алгоритм Крускала
procedure TMain.Button2Click (Sender: TObject);
var j, k, v2, Ves_gr: byte;
t1, t2, t, Sr, Pr: longint;
Tk: real; Y: Gr;
procedure UniteComponents (a, b: byte);
var i: byte;
begin
If a> b then begin inc (sr); Pr: = Pr +3; i: = a; a: = b; b: = i; end else inc (sr);
for i: = 1 to V do
If Mark [i] = b then begin Mark [i]: = a; inc (pr); end;
Sr: = Sr + V;
end;
procedure SortRebr (var X: Gr);
var i, n, j, numb: integer; Mx: TRebro;
begin
N: = R;
for i: = 1 to R-1 do
begin
Mx: = X [1];
numb: = 1;
Pr: = Pr +2;
For j: = 2 to N do
If X [j]. Vs> Mx.Vs then
begin
inc (Sr);
Pr: = Pr +2;
Mx: = X [j];
numb: = j;
end
else inc (sr);
X [numb]: = X [N];
X [N]: = Mx;
N: = N-1;
pr: = Pr +3;
end;
end;
begin
Y: = X;
t: = 0;
for k: = 1 to 100 do
begin
Sr: = 0; / / кількість порівнянь
Pr: = 0; / / к-ть присвоювання
Ves_gr: = 0;
SortRebr (X);
Label3.Caption :='';
t1: = timer;
for v2: = 1 to V do
Mark [v2]: = v2;
for j: = 1 to R do
If Mark [X [j]. Fst] <> Mark [X [j]. Lst] Then
Begin
Label3.Caption: = Label3.Caption + IntToStr (X [j]. Fst) + '' + IntToStr (X [j]. Lst) +
'' + IntToStr (X [j]. Vs) + # 13;
inc (sr);
Ves_gr: = Ves_gr + X [j]. Vs;
UniteComponents (Mark [X [j]. Fst], Mark [X [j]. Lst]);
end
else inc (Sr);
t2: = timer;
T: = t + t2-t1;
label12.Caption: = inttostr (Ves_gr);
label14.Caption: = inttostr (Pr);
label16.Caption: = inttostr (Sr);
X: = Y;
end;
Tk: = abs (t/100);
label6.Caption: = FloatToStr (Tk) + '* 0.01 c';
end;
/ / Алгоритм Прима
procedure TMain.Button3Click (Sender: TObject);
const MaxVes = 255;
var Mark: array [1 .. 10] of boolean;
D, Res: array [1 .. 10] of byte;
i, j, imin, min, k: byte;
t1, t2, t, Sr, Pr, Ves_gr: longint; TP: real;
Function FindVes (i, j: byte): byte;
var k: byte;
begin
k: = 0;
Repeat
inc (k);
Until (k> 16) or
((X [k]. Fst = i) and (X [k]. Lst = j))
or ((X [k]. Fst = j) and (X [k]. Lst = i));
if k> 16 then FindVes: = 255 else
FindVes: = X [k]. Vs;
end;
Function Aps (i, j: byte; var Ves: byte): boolean;
var k: byte;
begin
k: = 0; inc (pr);
Repeat
inc (k); inc (pr);
Until (k> R) or
((X [k]. Fst = i) and (X [k]. Lst = j))
or ((X [k]. Fst = j) and (X [k]. Lst = i));
if k> R then begin inc (sr); Aps: = false; end else
begin inc (sr); pr: = pr +2; Ves: = X [k]. Vs; Aps: = true end;
end;
Procedure Calc (i: byte);
Var j: byte;
Begin
For j: = 1 To V Do
If Not Mark [j] Then
If Aps (i, j, D [j]) Then begin Res [j]: = i; inc (pr); end;
inc (sr);
End;
begin
t: = 0;
for k: = 1 to 100 do
begin
Sr: = 0;
Pr: = 0;
Ves_gr: = 0;
t1: = timer;
Label7.Caption :='';
For i: = 1 To V Do begin
D [i]: = MaxVes; Mark [i]: = false; end;
Pr: = 2 * V;
Mark [4]: = True;
Calc (4);
For j: = 1 To V-1 Do Begin {каркас складається з n-1 ребер}
min: = MaxVes; inc (pr);
For i: = 1 To V Do
If Not Mark [i] Then
If min> D [i] Then Begin
Sr: = Sr +2; Min: = D [i]; imin: = i; pr: = pr +2;
End
else sr: = Sr +2
else inc (sr);
Mark [imin]: = True;
Calc (imin);
pr: = pr +2;
ves_gr: = ves_gr + FindVes (imin, Res [imin]);
label7.Caption: = Label7.Caption + IntToStr (imin) + '' + IntToStr (Res [imin]) +
'' + IntToStr (FindVes (imin, Res [imin ]))+# 13;
end;
label13.Caption: = inttostr (Ves_gr);
label15.Caption: = inttostr (Sr);
label17.Caption: = inttostr (Pr);
t2: = timer;
t: = t + t2-t1;
end;
TP: = abs (t/100);
Label8.Caption: = floattostr (TP) + '* 0.01 c';
end;
procedure TMain.N2Click (Sender: TObject);
begin
close;
end;
procedure TMain.N4Click (Sender: TObject);
begin
aboutbox.Show;
end;
end.
unit Unit2;
interface
uses Windows, SysUtils, Classes, Graphics, Forms, Controls, StdCtrls,
Buttons, ExtCtrls;
type
TAboutBox = class (TForm)
Panel1: TPanel;
ProgramIcon: TImage;
ProductName: TLabel;
Version: TLabel;
Copyright: TLabel;
Comments: TLabel;
OKButton: TButton;
procedure OKButtonClick (Sender: TObject);
private
{Private declarations}
public
{Public declarations}
end;
var
AboutBox: TAboutBox;
implementation
{$ R *. dfm}
procedure TAboutBox.OKButtonClick (Sender: TObject);
begin
close;
end;
end.
Література
Ахо А., Хопкрофта Дж., Ульман Дж. Структури даних і алгоритми. - М.: Видавничий будинок «Вільямс», 2001.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритми: побудова й аналіз. - М.: МЦНМО, 2001
Теорія графів Н. Кристофидес - «Світ» Москва, 1978
Методичні вказівки.