Hướng dẫn code duyệt theo DFS bằng ngôn ngữ C

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

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