[Thuật toán đồ thị / code C++] Thuật toán Euler - tìm đường đi Euler trên đồ thị G (với đồ thị nửa Euler)

Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy xác định mọi đường đi qua tất cả các cạnh mỗi cạnh chỉ qua duy nhất 1 lần.

Ý 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ó).

[Cài đặt thuật toán với Turbo 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();

}

/***** 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
- Khi download, bạn chờ 5s, click BỎ QUA QUẢNG CÁO (SKIN AD)