Thuật toán Hamilton - tìm chu trình Hamilton trên đồ thị G
Ý 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();
}
* Có thể bạn quan tâm:
- Những cuốn sách mà các bạn không thể bỏ qua khi còn trẻ
- Khoá học tin học văn phòng tốt nhất
Chúc các bạn thành công!