Алгоритм Крускала.
//---------------------------------------------------------------------------
#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. Вікіпедия: Алгоритм Крускала