#include <stdio.h>
#include <conio.h>
#define Tep "matranke.txt"
int a[50][50], n, chuaxet[50], truoc[50], so_canh_noi, DocFile();
void XuatMaTran(); // In ma tran ke ra man hinh
//int DocFile(); // Doc du lieu tu file
void DFS(int v); // Duyet theo chieu sau
void TimDuongDi(); // Tim duong di giua 2 dinh
void XuatMaTran()
// In ma tran ke ra man hinh
{
int i, j;
for (i = 0; i<n; i++)
{
for (j = 0; j<n; j++)
printf("%5d ", a[i][j]);
printf("\n");
}
} // XuatMaTran
int DocFile()
// Doc du lieu tu file:
// 1 - Thanh cong
// 0 - That bai
{
FILE *f;
int i, j;
f = fopen(Tep, "rt");
if (f == NULL)
{
printf("\nDoc file bi loi");
return 0;
}
// Bat dau doc du lieu
fscanf(f, "%d", &n);
for (i = 0; i<n; i++)
for (j = 0; j<n; j++)
fscanf(f, "%d", &a[i][j]);
fclose(f);
return 1;
} // DocFile()
void DFS(int v) //giai thuat tim kiem theo chieu sau
// Duyet theo chieu sau
{
int u;
chuaxet[v] = truoc[50],so_canh_noi;
for (u = 0; u<n; u++)
if ((a[v][u]>0) && (chuaxet[u] == 0))
{
truoc[u] = v;
DFS(u);
}
} // DFS()
void TimDuongDi()
// Tim duong di giua 2 dinh
{
int s, e, i, j;
printf("\Tim duong di tu dinh: ");
scanf("%d", &s);
printf("\nToi dinh:");
scanf("%d", &e);
s--;
e--;
// khoi tao so lieu
for (i = 0; i < n; i++){
truoc[i] = 0;
}
for (i = 0; i < n; i++)
{
chuaxet[i] = 0;
}
so_canh_noi = 1;
DFS(s);
// ket qua
if (chuaxet[e] == 0)
printf("\nKhong co duong di tu dinh %d toi dinh %d", s + 1, e + 1);
else
{
printf("\nDuong di tu dinh %d toi dinh %d:\n", s + 1, e + 1);
j = e;
printf("%d <== ", e + 1);
while (truoc[j] != s)
{
printf(" %d <== ", truoc[j] + 1);
j = truoc[j];
}
printf(" %d ", s + 1);
}
printf("\n");
} // TimDuongDi()
void main()
{
char chon;
tiep: clrscr();
if (!DocFile()) return;
XuatMaTran();
TimDuongDi();
printf("Ban co muon tiep tuc: c/k?? ");
scanf("%s",&chon);
if(chon=='c') goto tiep;
getch();
} // main()
Tags:
Môn học đại cương