Ý 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 Euler.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ó).
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define Filename "Euler.inp"
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
// Doc file chua do thi G (dang ma tran ke)
void Doc_File() {
int BacDinh; // Bac cua dinh
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 (do thi nua Euler)
SoCanh+=BacDinh;
cout<<endl;
}
fclose(f);
SoCanh = SoCanh/2; //so canh = so dinh chia 2
L = new int [SoCanh+1];
L[0] = XuatPhat;
}
// In ra duong di Euler
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<<"\n DUONG DI";
Try(1);
if(Dem==0)
cout<<"\n KHONG CO";
delete*A,L;
getch();
}
0 nhận xét:
Đăng nhận xét