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

Міністерство освіти і науки України

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

Курсова робота

З дисципліни

“Теорія алгоритмів та математична логіка”

На тему

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

Виконав студент

Факультету ЕлІТ групи ІН-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<n-1;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 %d\n”,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 %d\n”,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 <stdio. h>

#include <conio. h>

#include <time. h>

#include <values. h>

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<maxn;i++)

For (j = 0;j<maxn;j++)

A[i][j] = inf;

For (i =0;i< maxn; 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< nn;i++)

{

Fscanf(f,”%d %d %d”,&;x, &;y, &;z);

A[x-1][y-1] = z;

A[y-1][x-1] = z; // если неориентированный граф

}

Fclose(f);

}

Void prim()

{

}

Int main()

{

Clrscr();

Init();

Printf(“Min ostove derevo (by Prim)\n”);

Start= clock();

Prim();

End= clock();

Printf(“Vaga dereva = %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();

Return 0;

}

//—————————————————————————

Алгоритм Крускала.

//—————————————————————————

#include <vcl. h>

#pragma hdrstop

//—————————————————————————

#pragma argsused

//—————————————————————————

#include <stdio. h>

#include <conio. h>

#include <time. h>

#include <values. h>

Const int maxn = 10, maxm = 1000, inf = MAXINT/2, Max = 10000;

Typedef struct edge

{

Int x, y; // вершины ребра

Int w; // вес ребра

}eg;

Eg a[maxm]; // список ребер

Int s[maxn]; // размер компонент связности

Int r[maxn]; // связи вершин в компонентах связности

Int n, m; // кол-во вершин и ребер

Int mst_weight; // вес минимального остовного дерева

Int pr_count, sr_count; // кол-во присваиваний и сравнений

// инициализация и чтение данных

Void init()

{

Int i, 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 < m;i++)

{

Fscanf(f,”%d %d %d”,&;x, &;y, &;z);

A[i].x = x;

A[i].y = y;

A[i].w = z;

}

}

Void q_sort(int l, int r)

{

Int i, j, x;

I = l;

J = r;

X = a[l+rand()%(r-l+1)].w;

Do

{

While (i<=r &;&; x > a[i].w) i++;

While (j>=x &;&; x < a[j].w) j–;

If (i <= j)

{

If (i<j)

{

Eg buf;

Buf=a[i];

A[i]=a[j];

A[j]=buf;

}

I++;

J–;

}

} while (i <= j);

If (l < j) q_sort(l, j);

If (i < r) q_sort(i, r);

}

// построение mst (алгоритм Крускала)

Void kruskal()

{

}

Int main(int argc, char* argv[])

{

Clrscr();

Clock_t start, end;

Init();

Printf(“Min ostove derevo (by Kruskalo)\n”);

Start= clock();

Kruskal();

End = clock();

Printf(“Vaga dereva = %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();

Return 0;

}

//—————————————————————————

Література

1. Кормен Т., Лейзенсон Ч., Ривест Р. Алгоритмы: построрение и анализ. – М. : МЦНМО, 2001. – 960 с.

2. Вікіпедия: Алгоритм Прима

3. Вікіпедия: Алгоритм Крускала


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