//Thuat toan Prim
#include <stdio.h>
#include <conio.h>
#define MAX 100
#define input “g:/test2.txt”
typedef struct graph{
int n;
int a[MAX][MAX];
}DOTHI;
int DocDoThi(char text[MAX],DOTHI &g){
FILE *f;
f=fopen(text,”rt”);
if(f == NULL){
printf(“\n Khong tim duoc file”);
return 0;
}
fscanf(f,”%d”,&g.n);
for(int i=0; i<g.n;i++){
for(int j=0;j<g.n;j++)
fscanf(f,”%d”,&g.a[i][j]);
}
fclose(f);
return 1;
}
void XuatDoThi(DOTHI g){
printf(“\n So dinh cua ma tran la: %d”,g.n);
printf(“\n Ma Tran: \n”);
for(int i=0;i<g.n;i++){
printf(“\t”);
for(int j=0;j<g.n;j++)
printf(“%d “,g.a[i][j]);
printf(“\n”);
}
}
void DiTimCacDinhLienThong(DOTHI g, int nhan[MAX], int i){
for(int j=0;j<g.n;j++){
if(g.a[i][j] != 0 && nhan[j] != nhan[i]){
nhan[j]=nhan[i];
DiTimCacDinhLienThong(g,nhan,j);
}
}
}
int XetLienThong(DOTHI g){
int Nhan[MAX];
int i;
for(i=0;i<g.n;i++)
Nhan[i] = 0;
int SoThanhPhanLT = 0;
for(i=0;i<g.n;i++){
if(Nhan[i] == 0){
SoThanhPhanLT ++;
Nhan[i] = SoThanhPhanLT;
}
if(Nhan[i] != 0)
DiTimCacDinhLienThong(g,Nhan,i);
}
return SoThanhPhanLT;
}
int ChuaXet[MAX];
typedef struct EDGE{
int u;
int v;
int value;
}CANH;
CANH T[MAX];
void Prim(DOTHI g){
if(XetLienThong(g) != 1){
printf(“Do thi khong lien thong, do do khong thuc hien duoc thuat toan Prim tim cay khung nho nhat\n”);
return;
}
int nT=0;
for(int i=0;i<g.n;i++)
ChuaXet[i] = 0;
ChuaXet[0] = 1;
while(nT < g.n – 1){
CANH CanhNhoNhat;
int GiaTriNhoNhat = 100;
for(int i=0; i<g.n;i++){
if(ChuaXet[i] == 1){
for(int j=0; j<g.n;j++)
if(ChuaXet[j] == 0 && g.a[i][j] != 0 && GiaTriNhoNhat > g.a[i][j]){
CanhNhoNhat.u = i;
CanhNhoNhat.v = j;
CanhNhoNhat.value = g.a[i][j];
GiaTriNhoNhat = g.a[i][j];
}
}
}
T[nT] = CanhNhoNhat;
nT ++;
ChuaXet[CanhNhoNhat.v] = 1;
}
int TongTrongSoCuaCayKhung = 0;
printf(“Cay khung nho nhat cua do thi la \n”);
for(int i=0;i<nT-1;i++){
printf(“(%d,%d),”,T[i].u,T[i].v);
TongTrongSoCuaCayKhung += T[i].value;
}
printf(“(%d,%d).\n”,T[nT-1].u,T[nT-1].v);
TongTrongSoCuaCayKhung += T[nT-1].value;
printf(“Tong gia tri cua cay khung la %d\n”,TongTrongSoCuaCayKhung);
}
int main(){
DOTHI g;
if(DocDoThi(input,g) == 1){
printf(“\n Do thi doc thanh cong…”);
XuatDoThi(g);
printf(“\n Nhan mot phim bat ky de bat dau tim cay khung nho nhat…\n\n”);
getch();
Prim(g);
}
getch();
} |
