Ý 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 InputEuler.txt
- 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ụ:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define Filename "InputEluer.txt"
int Dem = 0, SoCanh=0; //dem so duong di va luu so canh cua do thi
int *L; //luu dinh da di qua
int **A,n;
int XuatPhat=0; //dinh xuat phat la dinh bac le neu do thi co dinh bac le
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; //xuat phat tu dinh bac le
SoCanh+=BacDinh;
cout<<endl;
}
fclose(f);
SoCanh = SoCanh/2; //so canh = so dinh chia 2
L = new int [SoCanh+1];
L[0] = XuatPhat;
}
// in duong di
void InDuongDi() {
Dem++;
cout<<endl<<XuatPhat+1;
for (int i = 1; i<=SoCanh; i++)
cout<<" -> "<<L[i]+1;
}
//thu tuc tim kiem de quy
void Try(int Canh) {
if(Canh > SoCanh) //tim du so canh thi xuat duong di
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; //xoa canh
Try(Canh+1); //tim canh tiep theo
A[L[Canh-1]][i]=A[i][L[Canh-1]]=1; //phuc hoi canh
L[Canh] = 0;
}
}
}
// ham chinh
void main() {
Doc_File();
cout<<"\nDUONG DI";
Try(1);
if(Dem==0)
cout<<" KHONG CO";
delete*A,L;
getch();
}
0 nhận xét:
Đăng nhận xét