Ứng dụng đường đi Hamilton

Một người khách du lịch muốn đi thăm n thành phố được đánh số từ 1 đến n, mỗi thành phố người khách chỉ muốn đi qua chúng một lần. Mạng lưới giao thông giữa n thành phố là hai chiều và được cho bởi ma trận A[i,j] trong đó A[i,j] =1 nếu có đường đi giữa thành phố i và thành phố j, A[i,j] = 0 trong trường hợp ngược lại.
Hãy viết chương trình thiết lập cho người khách một lộ trình (có thể tồn tại nhiều lộ trình) hay thông báo không tồn tại lộ trình theo yêu cầu của khách.
Dữ liệu vào: cho trong file Bai6.inp
- Dòng đầu ghi số n là số đỉnh của một đồ thị (0- Dòng 2 ghi đỉnh mà người khách du lịch xuất phát.
- Dòng i+2 (0 < i<=100) chứa n số A[i,1],A[i,2]…A[i,n] mỗi số cách nhau bởi một khoảng trắng.
Dữ liệu ra: In ra màn hình đường đi của người khách (nếu có).

Ví dụ:
Bai6.inp
5
1
0 1 0 0 0
1 0 1 1 1
0 1 0 1 0
0 1 1 0 1
0 1 0 1 0
Kết quả:1->2->3->4->5

Bai6.inp
6
1
0 1 1 0 0 0
1 0 1 0 1 0
1 1 0 0 0 1
0 0 0 0 1 0
0 1 0 1 0 0
0 0 1 0 0 0
Kết quả: KHONG TON TAI DUONG DI

Bai6.inp
5
2
0 1 0 1 1
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
1 1 0 1 0
Kết quả: 2->1->5->4->3

Code:

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define FileIn "Bai6.inp"
int Dem = 0;      //Dếm số đường đi
int*L;        //Lưu lại đường đi
char*DanhDau;  //Dánh dấu đỉnh đã đi
int **A,n,D;
/*Dọc file dữ liệu bài toán*/
void Doc_File() {
  FILE*f = fopen(FileIn,"rb");
  fscanf(f,"%d%d",&n,&D);      //Đọc n và đỉnh xuất phát lưu trong biến D
  cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<D<<endl;
  *A = new int [n];
  for(int i =0;i<n;i++) {
      A[i] = new int [n];
      for(int j =0;j<n;j++) {
        fscanf(f,"%d",&A[i][j]);
        cout<<A[i][j]<<" ";
      }
      cout<<endl;
  }
  fclose(f);
  D--;
}
/*Khởi tạo dữ liệu ban đầu cho bài toán*/
void KhoiTao() {
  DanhDau = new char [n];
  L = new int [n];
  for (int i = 0; i<n; i++) { 
      DanhDau[i] = 0;  //Khởi tạo mọi đỉnh chưa được đánh dấu
      L[i] = 0;
  }
  DanhDau[D] = 1;      //Đánh dấu đỉnh xuất phát
  L[0] = D;
}
/*In đường đi của bài toán ra màn hình*/
void InDuongDi(int Dinh) {
  Dem++;
  cout<<endl<<D+1;
  for (int i = 1; i<Dinh; i++)
      cout<<" -> "<<L[i]+1;
}
/*Tìm kiếm đường đi*/
void TimKiem(int Dinh) {
  if(Dinh == n && Dem == 0) InDuongDi(Dinh);
  else {
      for(int i = 0; i<n; i++)
      if( A[L[Dinh-1]][i]>0 && DanhDau[i] == 0 && Dem==0){
        L[Dinh] = i;
        DanhDau[i] = 1;  //Đánh dấu đỉnh tìm được
        TimKiem(Dinh+1);  //Tiếm kiếm đỉnh kế tiếp
        L[Dinh] = 0;
        DanhDau[i] = 0;  //Phục hồi đỉnh đánh dấu
      }
  }
}
/*Chương trình chính*/
void main() {
  clrscr();
  Doc_File();
  KhoiTao();
  cout<<"Duong Di Nguoi Khach";
  TimKiem(1);      //Tìm kiếm từ đỉnh thứ 2 của đồ thị
  if(Dem==0)
      cout<<" Khong Co";
  delete*A,DanhDau,L;
  getch();
}