Algoritmul lui Kruskal, folosind operatii cu multimi disjuncte

Arborele minim de acoperire (AMA) pentru un graf se defineste pentru grafuri neorientate si conexe (toate nodurile grafului se afla in aceeasi componenta conexa).

Dandu-se un graf conex si neorientat G=(V, E), unde V = multimea nodurilor, iar E multimea muchiilor grafului G, se numeste arbore minim de acoperire un graf conex si neorientat G' = (V, E'), unde E' inclus in E cu proprietatile:
- G' este este un arbore (graf aciclic);
- suma costurilor muchiilor din E' sa fie minima.

Dintre algoritmii clasici care se ocupa de determinarea arborelui minim de acoperire amintim: algoritmul Kruskal si algoritmul Prim.

=== Pseudocod ===

Fie G=(V, E), graf neorientat si conex
1) AMA = multimea vida
2) Pentru fiecare nod din V
creeaza_multime(v)
3) Sorteaza muchiile din E crescator dupa cost
4) Pentru fiecare muchie (u, v) din E in ordine crescatoare
- Daca gaseste_multime(u) != gaseste_multime(v)
a) Se adauga muchia (u, v) in AMA
b) reuneste(u, v)

=== Implementare in C ===

#include "stdio.h"
#include "stdlib.h"
#define MAX 100
#define INF -1

int n,m,**b;
typedef struct multime {
int c; //contorul multimii
int S[MAX]; //elementele multimii
} Set;

typedef struct muchie {
int x; int y; int cost;
} Muchie;

Muchie mu[MAX];
Set C[MAX]; //colectia
int nset; //nr de seturi

void citire()
{ FILE *f=fopen("in","r");
fscanf(f,"%d",&n);
int i,j,k,cost;
fscanf(f,"%d",&m); //nr muchii
for(i=0;i<=m-1;i++)
{ fscanf(f,"%d %d %d",&j,&k,&cost); mu[i].x=j; mu[i].y=k; mu[i].cost=cost; }
}


/* functii pt multimi disjuncte */

void Make_Set (int n)
{ int i; nset=n;
for(i=0; i<=n-1; i++)
{ C[i].c=1;
C[i].S[0]=i; }
}

void Print_Set()
{ int i,j;
for(i=0; i<=nset-1; i++)
{ for(j=0; j<=C[i].c-1 ; j++)
printf("%d ",C[i].S[j]);
printf("\n"); }
}

//identific a cata multime este multimea in care se afla un element
int Find(int x)
{ int j,i;
for(i=0;i<=nset-1;i++) // pt fiecare set
{ for(j=0; j<=C[i].c-1; j++)
if(x==C[i].S[j])
return i;
}
return -1;
}


void Set_Union(int a,int b) // reuniunea se face in C[a],se sterge C[b]
{ int i;
for(i=0;i<=C[b].c-1;i++)
if(Find(C[b].S[i])!=a)
{ C[a].S[C[a].c]=C[b].S[i]; C[a].c++; }
for(i=b; i<=nset-1; i++)
C[i]=C[i+1];
nset--;
}

void print_muchii()
{ int i;
for(i=0;i<=m-1;i++)
printf("%d %d %d \n",mu[i].x,mu[i].y,mu[i].cost);
}

Muchie arc_min() //gaseste arcul de cost minim si apoi il sterge!
{ int i,min=mu[0].cost,poz=0;
Muchie x=mu[0];
for(i=1; i<=m-1; i++)
if(mu[i].cost < min)
{ min=mu[i].cost; poz=i; x=mu[i]; }
for(i=poz; i<=m-2; i++)
mu[i]=mu[i+1];
m--;
return x;
}

void kruskal()
{
Make_Set(n);
Muchie a;
int u,v,i,j;
b=(int **)malloc(n*sizeof(int *));
for(i=0; i<=n-1; i++)
b[i]=(int *)malloc(n*sizeof(int));
for(i=0; i<=n-1; i++)
for(j=0; j<=n-1; j++)
{ if(i!=j)
b[i][j]=INF;
else
b[i][j]=0; }

int nm=0;
while (nm < n-1) // cat timp nu am atins n-1 muchii
{ a=arc_min();
u=a.x; v=a.y;
if(Find(u)!=Find(v)) // daca se afla in seturi diferite
{ Set_Union(Find(u),Find(v));
b[u][v]=a.cost; b[v][u]=a.cost; nm++; } //adaug muchie la graf nou
}
}

int *viz;

void afisare(int vf)
{
int i; viz[vf]=1;
printf("%d ",vf);

for(i=0; i<=n-1; i++)
if(b[vf][i]>=0 && viz[i]==0)
afisare(i);
}

void afisare2()
{ int i,j,w;
for(i=0; i<=n-1; i++)
for(j=i+1; j<=n-1; j++)
{ w=b[i][j];
if(w > 0)
printf("muchia %d-%d cost %d\n", i,j, w);
}
}

int main()
{ citire();
kruskal();
viz=(int *)malloc(n*sizeof(int));
int i;
for(i=0; i<=n-1 ;i++)
viz[i]=0;
afisare2();
free(viz);
return 0;
}