Thuật toán Eluer - tìm chu trình Eluer trên đồ thị G

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 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ụ:

[Cài đặt bài toán - code Turbo C++]

#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();
}