Thuật toán Euler - tìm đường đi Euler 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 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ó).
Thuật toán Euler - tìm đường đi Euler trên đồ thị G
#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();
}
/***** LƯU Ý ****/
- File Euler.inp được đặt ở thư mục chứa code [Download file Euler.inp tại đây], các bạn có thể tạo phải Euler.inp khác tùy vào đồ thị mà bạn muốn kiểm tra
- Download code chương trình tại đây
* 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
* Có thể bản quan tâm: [MMO] Hướng Dẫn *Kiếm Tiền Tự Động* Với Các Ứng Dụng Treo Máy *CỰC KỲ ĐƠN GIẢN VÀ HIỆU QUẢ*
Chúc các bạn thành công!