[Thuật toán đồ thị / code C++] Thuật toán Hamilton - tìm chu trình Hamilton trên đồ thị G

in , , , , , /

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ụ:

[Cài đặt bài toán - code Turbo C+]

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


Chúc các bạn thành công!