Реферат: Алгоритмы поиска остовного дерева Прима и Крускала
Министерствообразования и науки Украины
Сумскийгосударственный университет
Кафедра Информатики
Курсоваяработа
по дисциплине
“Теория алгоритмов и математическаялогика”
на тему:
“Алгоритмы поиска остовного дереваПрима и Крускала”
Сумы 2006
Содержание
Задание
Вступление
1. Теоретическая часть
2. Практическая реализация
Вывод
Программный код
Литература
Задание
Разработать программную реализациюрешения задачи о минимальном покрывающем дереве (построение минимального остова).Для нахождения минимального покрывающего дерева использовать алгоритмы Прима иКрускала.
/>
Исходная информация о ребрах графанаходится в текстовом файле 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, Е) и весовая функция 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 ребро соединяет различныекомпоненты графа Ga = (V,A), и с каждой итерацией цикла число компонент уменьшается на 1.Вначале каждая точка представляет собой отдельную компоненту; в конце весьостов — одна компонента, так что цикл повторяется |V| — 1 раз.
Теоретическая часть
Алгоритм Крускала
В любой момент работы алгоритма Крускаламножество А выбранных рёбер (часть будущего остова) не содержит циклов. Оносоединяет вершины графа в несколько связных компонент, каждая из которыхявляется деревом. Среди всех рёбер, соединяющих вершины из разных компонент,берётся ребро наименьшего веса. Надо проверить, что оно является безопасным.
Пусть (u, v) — такое ребро,соединяющее вершины из компонент С1 и C2 — Это реброявляется лёгким ребром для разреза (С1, V \C1).
Реализация алгоритма Крускала используетструктуры данных для непересекающихся множеств. Элементами множеств являютсявершины графа. Напомним, что 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)
8for для каждой вершины 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 ‑ 11 дерево состоит из единственной вершины 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;
procedureFormCreate(Sender: TObject);
procedureButton2Click(Sender: TObject);
procedureButton3Click(Sender: TObject);
procedureN2Click(Sender: TObject);
procedureN4Click(Sender: TObject);
private
{ Privatedeclarations }
public
{ Publicdeclarations }
end;
var
Main: TMain;
X:GR;
Mark:TVect;
R,V:byte;//кол-во ребери вершин соответственно
procedureLoadGraph;
implementation
{$R *.dfm}
FunctionTimer:longint;
constc60:longint=60;
varh,m,s,s100:word;
begin
decodetime(now,h,m,s,s100);
timer:=((h*c60+m)*c60+s)*100+s100;
end;
procedureLoadGraph;
varf:textfile;
i:byte;
begin
i:=1;
Assignfile(f,'dan.txt');
Reset(f);
R:=0;
V:=0;
Readln(f,R,V);
while noteof(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;
procedureTMain.FormCreate(Sender: TObject);
begin
LoadGraph;
end;
//Алгоритм Крускала
procedureTMain.Button2Click(Sender: TObject);
varj,k,v2,Ves_gr:byte;
t1,t2,t,Sr,Pr:longint;
Tk:real;Y:Gr;
procedureUniteComponents(a,b:byte);
var i:byte;
begin
If a>bthen begin inc(sr);Pr:=Pr+3;i:=a; a:=b; b:=i; end else inc(sr);
for i:=1 to Vdo
If Mark[i] =b then begin Mark[i]:=a;inc(pr);end;
Sr:=Sr+V;
end;
procedureSortRebr(var X:Gr);
var i,n,j,numb:integer;Mx:TRebro;
begin
N:=R;
for i:=1 toR-1 do
begin
Mx:=X[1];
numb:=1;
Pr:=Pr+2;
For j:=2 to Ndo
IfX[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 to100 do
begin
Sr:=0; //кол-во сравнений
Pr:=0; //кол-воприсваиваний
Ves_gr:=0;
SortRebr(X);
Label3.Caption:='';
t1:=timer;
for v2:=1 toV do
Mark[v2]:=v2;
for j:=1 to Rdo
IfMark[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.01c';
end;
//Алгоритм Прима
procedureTMain.Button3Click(Sender: TObject);
constMaxVes=255;
varMark: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;
FunctionFindVes(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>16then FindVes:=255 else
FindVes:=X[k].Vs;
end;
FunctionAps(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>Rthen begin inc(sr);Aps:=false; end else
begin inc(sr);pr:=pr+2;Ves:=X[k].Vs;Aps:=true end;
end;
ProcedureCalc(i: byte);
Var j: byte;
Begin
For j := 1 ToV Do
If NotMark[j] Then
IfAps(i,j,D[j]) Then begin Res[j] := i; inc(pr);end;
inc(sr);
End;
begin
t:=0;
for k:=1 to100 do
begin
Sr:=0;
Pr:=0;
Ves_gr:=0;
t1:=timer;
Label7.Caption:='';
For i := 1 ToV Do begin
D[i] :=MaxVes; Mark[i]:=false;end;
Pr:=2*V;
Mark[4] :=True;
Calc(4);
For j := 1 ToV-1 Do Begin { каркас состоитиз n-1 ребер }
min :=MaxVes; inc(pr);
For i := 1 ToV Do
If NotMark[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.01c';
end;
procedureTMain.N2Click(Sender: TObject);
begin
close;
end;
procedureTMain.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;
procedureOKButtonClick(Sender: TObject);
private
{ Privatedeclarations }
public
{ Publicdeclarations }
end;
var
AboutBox:TAboutBox;
implementation
{$R *.dfm}
procedureTAboutBox.OKButtonClick(Sender: TObject);
begin
close;
end;
end.
Литература
1. Ахо А., Хопкрофт Дж., Ульман Дж. Структурыданных и алгоритмы. — М.: Видавничий будинок «Вільямс», 2001.
2. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы:построение и анализ. — М.: МЦНМО, 2001
3. Теория графов Н. Кристофидес – «Мир»Москва, 1978
4. Методические указания.