Ý 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 xóa cạnh đã đi qua trong quá trình tìm kiếm đường đi.
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 Bai5.inp
- Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100)
- Dòng i+1 (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 cạnh (nếu có)
Ví dụ:
Cài đặt chương trình:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define Filename "Bai5.inp"
int Dem = 0, SoCanh=0;
int *L;
int **A,n;
int XuatPhat=0;
void Doc_File() {
int BacDinh;
FILE*f = fopen(Filename,"rb");
fscanf(f,"%d",&n);
cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<n<<endl;
*A = new int [n];
for(int i =0;i<n;i++) {
A[i] = new int [n];
BacDinh = 0;
for(int j =0;j<n;j++) {
fscanf(f,"%d",&A[i][j]);
cout<<A[i][j]<<" ";
if(A[i][j] == 1)
BacDinh++;
}
if(BacDinh%2==1)
XuatPhat = i;
SoCanh+=BacDinh;
cout<<endl;
}
fclose(f);
SoCanh = SoCanh/2;
L = new int [SoCanh+1];
L[0] = XuatPhat;
}
void InDuongDi() {
Dem++;
cout<<endl<<XuatPhat+1;
for (int i = 1; i<=SoCanh; i++)
cout<<" -> "<<L[i]+1;
}
void Try(int Canh) {
if(Canh > SoCanh)
InDuongDi();
else {
for(int i = 0; i<n; i++)
if( A[L[Canh-1]][i]>0){
L[Canh] = i;
A[L[Canh-1]][i]=A[i][L[Canh-1]]=0;
Try(Canh+1);
A[L[Canh-1]][i]=A[i][L[Canh-1]]=1;
L[Canh] = 0;
}
}
}
void main() {
Doc_File();
cout<<"\nDUONG DI";
Try(1);
if(Dem==0)
cout<<" KHONG CO";
delete*A,L;
getch();
}
Kết quả chạy chương trình:
Tags: Kỹ thuật lập trình, toán rời rạc, c, c++, euler, đồ thị, tìm đường đi