Hướng dẫn code duyệt theo DFS bằng ngôn ngữ C
| #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”);} } |
| int LuuVet[MAX]; int ChuaXet[MAX]; void DFS(int v,DOTHI g){ ChuaXet[v] = 1; int u; for(u = 0; u<g.n; u++ ){ if(g.a[v][u] != 0 && ChuaXet[u] == 0){ LuuVet[u] = v; DFS(u,g); } } } void duyettheoDFS(int S, int F, DOTHI g){ int i; for(i = 0; i< MAX; i++){ LuuVet[i] = -1; ChuaXet[i] = 0; } DFS(S,g); if(ChuaXet[F] == 1){ printf(“Duong di tu dinh %d den dinh %d la: \n\t”,S,F); i = F; printf(“%d”,F); while(LuuVet[i] != S){ printf(“<-%d”,LuuVet[i]); i = LuuVet[i]; } printf(“<-%d\n”,LuuVet[i]); } else{ printf(“Khong co duong di tu dinh %d den dinh %d \n”,S,F); } } int main(){ DOTHI g; if(DocDoThi(input,g) == 1){ printf(“\n Do thi doc thanh cong…”); XuatDoThi(g); printf(“Nhap mot phim bat ki de bat dau duyet theo DFS..\n\n”); getch(); duyettheoDFS(0,2,g); } getch(); } |
