Міністерствоосвіти і науки України
СумськийДержавний Університет
Курсова робота
з дисципліни
«Теоріяалгоритмів та математична логіка»
На тему
«Знаходженнямінімального остовом дерева. Порівняння алгоритму Прима і алгоритму Крускала»
Виконавстудент
факультетуЕлІТ групи ІН-83
ГорбатенкоО. О.
ПеревіривКузіков Б. О.
Суми 2010
Завдання роботи
Привиконанні ОДЗ необхідно реалізувати алгоритми Прима та Крускала побудовиостового дерева у графі, та протестувати її на тестовому графі наведеному узавданнях до ОДЗ згідно вашого варіанту. У пояснювальній записці до ОДЗ повиннобути викладено наступне:
•Вступ. Короткі відомості про поняття остового дерева;
•Завдання роботи, Включаючи тестовий приклад графу, згідно варіанта;
•Алгоритм Прима:
◦короткі відомості про алгоритм та асимптотичну оцінку його швидкодії, спосібпредставлення графу та його обґрунтування (10%);
◦остове дерево, отримане за допомогою алгоритму (5%);
◦фактичні параметри швидкодії (кількість порівнянь) для тестового прикладу(10%);
◦оцінку швидкодії реалізованого варіанта алгоритму (10%).
•Алгоритм Крускала:
◦короткі відомості про алгоритм та асимптотичну оцінку його швидкодії, спосібпредставлення графу та його обґрунтування(10%);
◦остове дерево, отримане за допомогою алгоритму (5%);
◦фактичні параметри швидкодії (кількість порівнянь) для тестового прикладу(10%);
◦оцінку швидкодії реалізованого варіанта алгоритму (10%).
•Порівняння алгортимів, контрольні приклади:
◦висновок що до умов, коли доцільно використовувати той чи інший алгоритм (10%)
◦довільний граф (10 або більше вершин), на якому алгоритм Прима дає перевагу,навести фактичні параметри швидкодії (10%);
◦довільний граф (10 або більше вершин), на якому алгоритм Крускала дає перевагу,навести фактичні параметри швидкодії (10%).
Поставленезавдання: маючи на вході граф G, одержати навиході його остовне дерево мінімальної вартості, використати алгоритми Крускалай Прима. Порівняти використовувані алгоритми./>
Вступ
НехайG = (V, Е) — зв’язний граф, у якому кожне ребро (u,v ) позначено числом c(u,v), що називається вартістю ребра. Остовним деревом графа G називається вільнедерево, що містить всі вершини V графа G. Вартість остовного дереваобчислюється як сума вартостей всіх ребер, що входять у це дерево.
Типовезастосування остовних дерев мінімальної вартості можна знайти при розробцікомунікаційних мереж. Тут вершини графа представляють міста, ребра — можливікомунікаційні лінії між містами, а вартість ребер відповідає вартостікомунікаційних ліній. У цьому випадку остовне дерево мінімальної вартостіпредставляє комунікаційну мережу, що поєднує всі міста комунікаційними лініямимінімальної вартості.
Існуютьрізні методи побудови остовних дерев мінімальної вартості. Багато хто з нихґрунтуються на наступній властивості остовних дерев мінімальної вартості. НехайG = (V, Е) — зв’язний граф із заданою функцією вартості, що задана на множиніребер. Позначимо через U підмножину вершин V. Якщо (і, v) — таке ребронайменшої вартості, що й належить U і v належить V \ U, тоді для графа G існуєостовное дерево мінімальної вартості, що містить ребро (і, v).
Існуютьдва популярних алгоритми побудови остовного дерева мінімальної вартості дляпозначеного графа G = (V, Е), основані на описаній властивості: Прима йКрускала. Обидва алгоритми відповідають «жадібній» стратегії: на кожному кроцівибирається локально найкращий варіант.
Алгоритм Прима
АлгоритмПрима поступово будує шуканий мінімальний остов, додаючи до нього по одномуребру на кожному кроці (Це означає, що алгоритм Прима є жадібним. Більш того,справедливість алгоритму Прима легко встановлюється в рамках теоріїматроідов.). На початку роботи алгоритму результуюче дерево складається зоднієї вершини (її можна вибирати довільно). Алгоритм складається з N-1ітерації, на кожній з яких до дерева додається рівно одне ребро, не порушуєвластивості дерева (тобто один кінець додається ребра належить дереву, а інший- не належить). Ключовий момент — з усіх таких ребер кожен раз вибираєтьсяребро з мінімальною вагою. Така реалізація працює за O (MN).
Покращенареалізація буде виконуватися помітно швидше — за O (M log N + N2).
Для цього мивідсортуємо всі ребра в списках суміжності кожної вершини по збільшенню ваги(буде потрібно O (M log M) = O (M log N)). Крім того, для кожної вершинизаведемо покажчик, який вказує на перше доступне ребро в її списку суміжності.Спочатку всі покажчики вказують на початку списків, тобто рівні 0.На i-ої ітерації алгоритму Прима ми перебираємовсі вершини, і вибираємо найменше за вагою ребро серед доступних. Оскільки всіребра вже відсортовані за вагою, а покажчики вказують на перші доступні ребра,то вибір найменшого ребра здійсниться за O (N). Тепер нам слід оновитипокажчики, оскільки деякі з них вказують на що стали недоступними ребра (обидвакінці яких опинилися всередині дерева), тобто зрушити деякі з них праворуч.Проте, оскільки у всіх списках суміжності в сумі 2 * M елементів, а покажчикизсуваються тільки вправо, то виходить, що на підтримку всіх покажчиків потрібноO (M) дій. Разом — час виконання алгоритму O (MlogM + N2 + M), тобто O (M log N+ N2)
Кодалгоритму:
void prim()
{
inti, min, j, k;
pr_count=0;
sr_count=0;
k= 0;
v[0]=1;
for(i = 1;i
{
d[i]= a[i][0];
p[i]= 0;
}
for(i = 0;i
{
min= inf;
for(j = 0;j
if((v[j]!=1) && (d[j]
{
sr_count++;
min= d[j];
pr_count++;
k= j;
pr_count++;
}
printf(“%d%d\n”,k+1, p[k]+1);
mst_weight+=a[k][p[k]];
v[k]= 1;
for(j = 0;j
if((v[j]!=1) && (d[j] > a[k][j]))
{
sr_count++;
p[j]= k;
pr_count++;
d[j]= a[k][j];
pr_count++;
}
}
}
Результатроботи програми:
/>
АлгоритмКрускала
АлгоритмКрускала спочатку поміщає кожну вершину в своє дерево, а потім поступовооб’єднує ці дерева, об’єднуючи на кожній ітерації два деяких дерева деякимруба. Перед початком виконання алгоритму, усі ребра сортуються за вагою (впорядку неубиванія). Потім починається процес об’єднання: перебираються всіребра від першого до останнього (у порядку сортування), і якщо у поточногоребра його кінці належать різним піддерев, то ці піддерев об’єднуються, а ребрододається до відповіді. Після закінчення перебору всіх ребер всі вершиниопиняться належать одному піддереві, і відповідь знайдений.
Сортуванняребер потребують O (M log N) операцій. Приналежність вершини того чи іншогопіддереві зберігається просто за допомогою масиву, об’єднання двох деревздійснюється за O (N) простим проходом по масиву. Враховуючи, що всьогооперацій об’єднання буде N-1, ми й отримуємо асимптотики O (M log N + N2).
Покращенареалізація використовує структуру даних «Система непересічних множин»позволет домогтися асимптотики O (M log N). Так само, як і в простій версіїалгоритму Крускала, відсортуємо усі ребра по неубиванію ваги. Потім помістимокожну вершину в своє дерево (тобто своє безліч) на це піде в сумі O (N). Перебираємоусі ребра (у порядку сортування) і для кожного ребра за O (1) визначаємо, чиналежать його кінці різних деревам (за допомогою двох викликів FindSet за O(1)). Нарешті, об’єднання двох дерев буде здійснюватися викликом Union — такожза O (1). Разом ми отримуємо асимптотики O (M log N + N + M) = O (M log N).
voidkruskal()
{
intk, i, p, q;
pr_count=0;
sr_count=0;
q_sort(1,m);
//сортируем список ребер по неубыванию
for(i = 0;i
{
r[i]= i; // у вершина своя компонента связности
s[i]= 0; // размер компоненты связности
}
k= 0; // номер первого ребра + 1
for(i = 0;i
{
do
{// ищем ребра из разных
k++;// компонент связности
p= a[k].x;
pr_count++;
q= a[k].y;
pr_count++;
while(r[p]!=p) // ищем корень для p //
{
sr_count++;
p= r[p];
pr_count++;
}
while(r[q]!=q) // ищем корень для q }
{
sr_count++;
q= r[q];
pr_count++;
}
}while(p==q);
printf(“%d%d\n”,a[k].x, a[k].y); // вывод ребра
mst_weight+=a[k].w;
if(s[p]
{// компоненты связности
r[p]= q;
pr_count++;
s[q]= s[q] + s[p];
pr_count++;
}
else
{
r[q]= p;
pr_count++;
s[p]= s[p] + s[q];
pr_count++;
}
}
}
Результатроботи програми:
/>
Врезультаті виконання програм ми переконалися, що вони дають однакове мінімальнеостове дерево, яке має вигляд:
/>
Висновок.Якщо кількість вершин достатньо мала, то доцільнішевикористовувати алгоритм Прима, в іншому випадку доцільно користуватисяалгоритмом Крускала.
Кодпрограм
АлгоритмПрима.
#include
#include
#include
#include
constint maxn = 100, inf = MAXINT/2, Max = 10000;
inta[maxn][maxn], p[maxn], z;
intv[maxn];
intd[maxn], n, mst_weight, pr_count, sr_count;
clock_tstart, end;
voidinit()
{
inti, j, x, y, nn, z;
FILE*f;
mst_weight= 0;
for(i = 0;i
for(j = 0;j
a[i][j]= inf;
for(i =0;i
{
v[i]=0;
d[i]=0;
p[i]=0;
}
f=fopen(«input.txt»,«rt»);
fscanf(f,”%d”,&n);
fscanf(f,”%d”,&nn);
for(i = 0;i
{
fscanf(f,”%d%d %d”,&x, &y, &z);
a[x-1][y-1]= z;
a[y-1][x-1]= z; // если неориентированный граф
}
fclose(f);
}
voidprim()
{
}
intmain()
{
clrscr();
init();
printf(«Minostove derevo (by Prim)\n»);
start=clock();
prim();
end=clock();
printf(«Vagadereva = %d\n», mst_weight);
printf(«Time= %f\n», (end-start)/CLK_TCK);
printf(«Comparison= %d\n», pr_count);
printf(«Assignment= %d \n», sr_count);
getch();
return0;
}
//—————————————————————————
АлгоритмКрускала.
//—————————————————————————
#include
#pragmahdrstop
//—————————————————————————
#pragmaargsused
//—————————————————————————
#include
#include
#include
#include
constint maxn = 10, maxm = 1000, inf = MAXINT/2, Max = 10000;
typedefstruct edge
{
intx, y; // вершины ребра
intw; // вес ребра
}eg;
ega[maxm]; // список ребер
ints[maxn]; // размер компонент связности
intr[maxn]; // связи вершин в компонентах связности
intn, m; // кол-во вершин и ребер
intmst_weight; // вес минимального остовного дерева
intpr_count,sr_count; // кол-во присваиваний и сравнений
//инициализация и чтение данных
voidinit()
{
inti, j, x, y, nn, z;
FILE*f;
mst_weight= 0;
f=fopen(«input.txt»,«rt»);
fscanf(f,”%d”,&n);
fscanf(f,”%d”,&m);
for(i = 0; i
{
fscanf(f,”%d%d %d”,&x, &y, &z);
a[i].x= x;
a[i].y= y;
a[i].w= z;
}
}
voidq_sort(int l,int r)
{
inti, j, x;
i= l;
j= r;
x= a[l+rand()%(r-l+1)].w;
do
{
while(i a[i].w) i++;
while(j>=x && x
if(i
{
if(i
{
egbuf;
buf=a[i];
a[i]=a[j];
a[j]=buf;
}
i++;
j–;
}
}while (i
if(l
if(i
}
//построение mst (алгоритм Крускала)
voidkruskal()
{
}
intmain(int argc, char* argv[])
{
clrscr();
clock_tstart, end;
init();
printf(«Minostove derevo (by Kruskalo)\n»);
start=clock();
kruskal();
end= clock();
printf(«Vagadereva = %d\n», mst_weight);
printf(«Time= %f\n», (end-start)/CLK_TCK);
printf(«Comparison= %d\n», pr_count);
printf(«Assignment= %d \n», sr_count);
getch();
return0;
}
//—————————————————————————
Література
1. Кормен Т.,Лейзенсон Ч., Ривест Р. Алгоритмы: построрение и анализ. — М.: МЦНМО, 2001. — 960 с.
2. Вікіпедия:Алгоритм Прима
3. Вікіпедия:Алгоритм Крускала