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

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;