Thuật toán Hamilton - tìm chu trình Hamilton trên đồ thị G

Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy xác định mọi đường đi từ đỉnh xuất phát đi qua tất cả các đỉnh mỗi đỉnh chỉ qua duy nhất 1 lần.



Ý tưởng thuật toán: sử dụng kỹ thuật tìm kiếm theo chiều sâu bằng cách đánh dấu đỉnh đã đi qua trong quá trình tìm kiếm.
+ Mô tả dữ liệu đầu vào và đầu ra của bài toán:
+ Dữ liệu vào: cho trong tập tin Bai4.inp
  - Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100)
  - Dòng 2 ghi đỉnh xuất phát.
  - Dòng i+2 (1 < i < n ) 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 qua tất cả các đỉnh (nếu có).

Ví dụ:

#include <stdio.h>

#include <conio.h>

#include <iostream.h>

#define FileIn "InputHamitol.txt"

int Dem = 0; //dem so duong di

int *L; //luu duong di

char *DanhDau; //danh dau dinh da di

int **A,n,D;

//doc du lieu tu tap tin theo yeu cau cua bai toan

void Doc_File() {

      FILE*f = fopen(FileIn,"rb");

      fscanf(f,"%d%d",&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--;

}

//khoi tao du lieu ban dau cho bai toan

void KhoiTao() {

   DanhDau = new char [n];

   L = new int [n];

   for (int i = 0; i<n; i++) {

      DanhDau[i] = 0; //tat ca cac dinh dieu danh dau

      L[i] = 0;

   }

   DanhDau[D] = 1; //danh dau dinh xuat phat

   L[0] = D;

}

//xuat duong di ra man hinh

void InDuongDi(int Dinh) {

   Dem++;

   cout<<endl<<D+1;

   for (int i = 1; i<Dinh; i++)

      cout<<" -> "<<L[i]+1;

 }

//tim kiem duong di

void Try(int Dinh) {

   if(Dinh == n)

      InDuongDi(Dinh);

    else {

           for(int i = 0; i<n; i++)

                 if( A[L[Dinh-1]][i]>0 && DanhDau[i] == 0){

                         L[Dinh] = i;

                         DanhDau[i] = 1; //danh dau dinh da di qua

                         Try(Dinh+1); //tim kiem dinh tiep theo

                         L[Dinh] = 0;

                        DanhDau[i] = 0; //phuc hoi dinh da danh dau

     }

  } 

}

void main() {

   clrscr();

   Doc_File();

   KhoiTao();

   cout<<"Duong di";

   Try(1);

    if(Dem==0)

          cout<<" khong co.";

    delete*A,DanhDau,L;

    getch();

}