Знаходження мінімального остовом дерева. Порівняння алгоритму Прима і алгоритму Крускала

Міністерство освіти і науки України
Сумський Державний Університет

Курсова робота
з дисципліни
«Теорія алгоритмів та математична логіка»
На тему
«Знаходження мінімального остовом дерева. Порівняння алгоритму Прима і алгоритму Крускала»

Виконав студент
факультету ЕлІТ групи ІН-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()
{
int i, min, j, k;
pr_count=0;
sr_count=0;
k = 0;
v[0]= 1;
for (i = 1;i< n;i++)
{
d[i] = a[i][0];
p[i] = 0;
}
for (i = 0;i {
min = inf;
for (j = 0;j< n;j++)
if ((v[j]!=1) && (d[j] < min))
{
sr_count++;
min = d[j];
pr_count++;
k = j;
pr_count++;
}
printf(%d %dn»,k+1, p[k]+1);
mst_weight+=a[k][p[k]];
v[k] = 1;
for (j = 0;j< n;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).
void kruskal()
{
int k, i, p, q;
pr_count=0;
sr_count=0;
q_sort(1, m);
// сортируем список ребер по неубыванию
for (i = 0;i< n;i++) // цикл по вершинам
{
r[i] = i; // у вершина своя компонента связности
s[i] = 0; // размер компоненты связности
}
k = 0; // номер первого ребра + 1
for (i = 0;i< n-1;i++) // цикл по ребрам mst
{
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 %dn»,a[k].x, a[k].y); // вывод ребра
mst_weight+=a[k].w;
if (s[p] < s[q]) // взвешенное объединение
{ // компоненты связности
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
const int maxn = 100, inf = MAXINT/2, Max = 10000;
int a[maxn][maxn], p[maxn], z;
int v[maxn];
int d[maxn], n, mst_weight, pr_count, sr_count;
clock_t start, end;
void init()
{
int i, 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< maxn; i++)
{
v[i]=0;
d[i]=0;
p[i]=0;
}
f=fopen(«input.txt»