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

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