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(); } |
