Giải Thuật Prim

#include <stdio.h>
#include <limits.h>


main(){
int a[100][100];
int k[100];
int p[100];
int tam[100];

int i;
int j;
int s,l,u,v,n,m;

FILE *f=fopen("prim.txt","r");
fscanf(f,"%d %d ",&n,&m);

for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
a[i][j]=0;

p[i]=0;
tam[i]=INT_MAX;
k[i]=0;
}


for(i=1;i<=m;i++){
fscanf(f,"%d %d %d ",&u,&v,&l);
a[u][v]=l;
a[v][u]=l;
}

fclose(f);

s=6; //chon dinh
k[s]=1;  // dinh da chon la =1
p[s]=-1;  //k co dinh truoc no

for(i=1;i<=n;i++){
if(a[s][i]>0 && i!=s){

tam[i]=a[s][i];
p[i]=s;
}
}

int num=1;
int w=0;
int min,minw;
while (num<n){
min=INT_MAX;
minw=0;


for(i=1;i<=n;i++){
if(k[i]== 0 && tam[i]<min)

min=tam[i],
minw=i;

}

k[minw]=1;
num++;
w+=tam[minw];
printf("%d -> %d %d \n",p[minw],minw,tam[minw]);
for(i=1;i<=n;i++){
if(k[i]==0 && a[minw][i]>0 && a[minw][i]<tam[i])

 tam[i]=a[minw][i],
 p[i]=minw;

}
}

printf(" w= %d\n",w);
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
printf("%2d ",a[i][j]);
}
printf("\n");
}

FILE *f1=fopen("outputPrim.txt","w");
fprintf(f1," w= %d\n",w);

for(i=1;i<=n;i++){
if(i!=s)
fprintf(f1,"%d -> %d",p[i],i);
fprintf(f1,"\n");


}
}