Kruskal

I suggest to use Union-Find for kruskal.

struct T
{
long x;
long y;
long weight;
};

T a[1000009];

int cmp( const void *a, const void *b )
{
T *p = (T *)a;
T *q = (T *)b;

return ( p->weight – q->weight );
}

for(i=1;i<=n;i++) // n number of node
P[i]=-1;

for(i=0;i<m;i++) // m number of edge
scanf(“%ld %ld %ld”,&a[i].x,&a[i].y,&a[i].weight);

qsort(a,m,sizeof(T),cmp);

cost = 0;

for(i=0;i<m;i++)
{
x = Parent(a[i].x);
y = Parent(a[i].y);
if(x!=y)
{
cost+=a[i].weight;
P[x]=y;
}
}

printf(“%ld\n”,cost);

Advertisements