Hướng dẫn code thuật toán Kruskal bằng ngôn ngữ c

14/12/2021 0 nhận xét Thuộc mụcC

Hướng dẫn code thuật toán Kruskal bằng ngôn ngữ c

Bạn nhập ma trận bên dưới vào một tập tin có đuôi txt và lưu nó trên ô đĩa phù hợp với phần define trong đoạn code bên dưới.

#include <stdio.h>
#include <conio.h>
#define MAX 100
#define input “g:/test.txt”
typedef struct graph{
int n;
int a[MAX][MAX];
}DOTHI;
typedef struct EDGE{
int u;
int v;
int value;
}CANH;
int DocDoThi(DOTHI &g,char text[MAX]){
FILE *f;
f=fopen(text,”rt”);
if(f==NULL){
printf(“\n Khong tim thay tai lieu”);
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: %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 SapXepTang(CANH E[100], int tongsocanh){
CANH canhtam;
for(int i=0;i<tongsocanh-1;i++){
for(int j=i+1;j<tongsocanh;j++)
if(E[i].value >E[j].value){
canhtam = E[i];
E[i] = E[j];
E[j] = canhtam;
}
}
}
void Kruskal(DOTHI g){
CANH listEdge[MAX];
int tongsocanh = 0;
int i,j;
for(i=0;i<g.n;i++){
for(j=i+1;j<g.n;j++)
if(g.a[i][j]>0){
listEdge[tongsocanh].u = i;
listEdge[tongsocanh].v = j;
listEdge[tongsocanh].value = g.a[i][j];
tongsocanh++;
}
}
SapXepTang(listEdge,tongsocanh);
int nT = 0;
CANH T[MAX];
int nhan[MAX];
for(i=0;i<g.n;i++)
nhan[i] =i;
int canhdangxet = 0;
while(nT <g.n && canhdangxet <tongsocanh){
if(nhan[listEdge[canhdangxet].u] != nhan[listEdge[canhdangxet].v]){
T[nT] = listEdge[canhdangxet];
nT++;
int giatri = nhan[listEdge[canhdangxet].v];
for(j=0;j<g.n;j++)
if(nhan[j]==giatri)
nhan[j] = nhan[listEdge[canhdangxet].u];
}
canhdangxet++;
}
if(nT != g.n-1)
printf(“\nDo thi khong lien thong \n”);
else{
int TongTrongSoCuaCayKhung = 0;
printf(“\nDo thi lien thong\n”);
printf(“Cay khung nho nhat cua do thi la \n”);
for(i=0;i<nT;i++){
printf(“(%d,%d)”,T[i].u,T[i].v);
TongTrongSoCuaCayKhung += T[i].value;
}
printf(“\nTong gia tri cua cay khung la %d\n”,TongTrongSoCuaCayKhung);
}
}
int main(){
DOTHI g;
if(DocDoThi(g,input) == 1){
printf(“\n Doc do thi thanh cong”);
XuatDoThi(g);
printf(“\n Bam 1 phim bat ki de bat dau tim cay khung nho nhat theo thuat toan kruskal …\n\n”);
getch();
Kruskal(g);
}
getch();
}