Bài 5. Đường đi Euler

Đường đi Euler

Một lưới giao thông hai chiều giữa n địa điểm được cho bởi ma trận A[i,j] trong đó A[i,j]=1 nếu có đường đi từ i đến j, còn A[i,j] = 0 trong trường hợp ngược lại. Một người đưa thơ cần đi qua tất cả các con đường này để phát thơ, mỗi đường chỉ qua một lần. Hãy xác định một lộ trình của người đưa thơ này (có thể tồn tại nhiều lộ trình khác nhau) hay thông báo không tồn tại đường như vậy.
Dữ liệu vào: cho trong file Bai5.inp.
- Dòng đầu ghi số n là số đỉnh của một đồ thị (0- Dòng i+1 (0Dữ liệu ra: In ra màn hình đường đi của người đưa thơ (nếu có).
Input 1:
5
0 1 0 0 0
1 0 1 1 1
0 1 0 1 0
0 1 1 0 1
0 1 0 1 0
Output 1:
1->2->3->4->2->5->4
Input 2:
5
0 1 0 0 0
1 0 1 1 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 0
Output 2:
KHONG TON TAI DUONG DI
Input 3
5
0 1 0 0 1
1 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
Output 3:
2->1->5->4->2->3->4

HƯỚNG DẪN THUẬT TOÁN
Bài toán 3 chính là bài toán tìm đường đi Euler. Điều kiện để có đường đi Euler là:
- Đồ thị liên thông.
- Đồ thị có không quá 2 đỉnh bậc lẻ. Nếu có 2 đỉnh bậc lẻ thì đỉnh xuất phát tìm đường đi phải là đỉnh bậc lẻ.
Ý tưởng thuật toán: Sử dụng kỹ thuật xoá cạnh. Nghĩa là, khi ta đi qua bất kỳ cạnh nào ta phải xoá cạnh tương ứng bằng cách gán trọng số đường đi của cạnh mới đi qua bằng 0. Thuật toán kết thúc khi ta đi qua tất cả các cạnh của đồ thị khi đó ma trận trận liên kết của đồ thị bằng 0.
HƯỚNG DẪN CÀI ĐẶT
 Cài đặt hàm kiểm tra tính liên thông của đồ thị nếu liên thông trả về kết quả 1 ngược lại trả về kết quả 0.
 Cài đặt hàm kiểm tra đồ thị có thỏa mãn tồn tại không quá 2 đỉnh bậc lẻ nếu thỏa mãn trả về kết quả 1 ngược lại trả về kết quả 0. Nếu tồn tại đỉnh bậc lẻ thì đỉnh bậc lẻ chính là đỉnh xuất phát và trong quá trình kiểm tra chúng ta đếm luôn số cạnh của đồ thị. Bởi vì thuật toán kết thúc khi ta đi hết tất cả mọi cảnh của đồ thị.
 Cài đặt thuật toán tìm đường đi Euler: trước tiên kiểm tra xem đồ thị co thỏa mãn điều kiện tồn tại đường đi Euler hay chưa nếu không thỏa mãn thì thuật toán kết thúc. Ngược lại ta tìm đường đi Euler như sau:
- Chọn đỉnh xuất phát: nếu tồn tại đỉnh bậc lẻ thì chọn đỉnh bậc lẻ làm đỉnh xuất phát, nếu không tồn tại đỉnh bậc lẻ thì chọn 1 đỉnh bất kỳ thông thường ta chọn đỉnh đầu tiên làm đỉnh xuất phát.
- Từ đỉnh xuất phát ta đi tới đỉnh kề nó (A[xuất phát][kề]=1) và xóa cạnh tương ứng. Nếu j là đỉnh kề với đỉnh xuất phát thì ta xoá cạnh bằng cách gán A[xuất phát][j]= A[j][xuất phát] = 0 và đỉnh xuất phát gán bằng đỉnh j. Lặp lại cho đến khi không còn đi được nữa (đi qua mọi cạnh của đồ thị) thì thuật toán kết thúc.
CÀI ĐẶT ĐỆ QUY

Code:

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define Filename "Bai5.inp"
/*Khai báo các biến toàn cục*/
int Dem = 0;      //Đếm số đường đi
int*L;         //Lưu lại đỉnh đã đi
int **A,n      
int XuatPhat=0;    //Đỉnh xuẩt phát tìm kiếm là đỉnh bậc lẻ nếu đồ thị có đỉnh bậc lẻ
int SoCanh=0;      //Lưu số cạnh của đồ thị vì đường đi đi qua tất cả các cạnh
/*Dọc file dữ liệu và khởi tạo ban đầu*/
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;      //Xuẩt phát là đỉnh bậc lẻ
      SoCanh+=BacDinh;
      cout<<endl;
   }
   fclose(f);
   SoCanh = SoCanh/2;         //Số cạnh = tổng bậc /2
   L = new int [SoCanh+1];      //Khởi tạo lưu đỉnh
   L[0] = XuatPhat;
}
/*Xuất đường đi tìm được ra màn hình*/
void InDuongDi() {
   Dem++;
   cout<<endl<<XuatPhat+1;
   for (int i = 1; i<=SoCanh; i++)
      cout<<" -> "<<L[i]+1;
}
/*Thủ tục tìm kiếm đệ quy*/
void TimKiem(int Canh) {
   /*Tìm cho đến khi cạnh tìm được lớn hơn số cạnh của đồ thị mới xuất đường đi*/
   if(Canh > SoCanh && Dem ==0 ) InDuongDi();   
   else {
      for(int i = 0; i<n; i++)
      if( A[L[Canh-1]][i]>0 && Dem==0){
         L[Canh] = i;
         A[L[Canh-1]][i]=A[i][L[Canh-1]]=0;   //Xóa cạnh
         TimKiem(Canh+1);            //Tìm đỉnh tiếp theo
         A[L[Canh-1]][i]=A[i][L[Canh-1]]=1;   //Phục hồi cạnh
         L[Canh] = 0;
      }
   }
}
void main() {
   Doc_File();
   cout<<"\nDUONG DI";
   TimKiem(1);
   if(Dem==0)
      cout<<" KHONG CO";
   delete*A,L;
   getch();
}


Được sửa bởi Admin ngày Thu May 26, 2011 8:34 am; sửa lần 2.

Ý tưởng giải thuật khá hay. Tuy nhiên trong lúc cài đặt thì lại chọn "đệ quy, quay lui". Theo mình nghĩ đệ quy thì cũng tốt nhưng không nhất thiết phải quay lui, vì quay lui rất tốn thời gian. Để không phải quay lui ta nên thêm hàm kiểm tra tính liên thông vào nữa là được, nhưng vấn đề là dùng giải thuật nào để kiểm tra tính liên thông, không khéo nó con chậm hơn quay lui nữa. Đúng là nhức cái đầu.

Sử dụng duyệt theo chiều rộng hay chiều sâu cũng được nhưng mình làm cho nó phong phú hơn thui. hihi... Các bạn thử khử đệ quy cho bài toán này nhé!

Ui, bài này debug bằng Visual Studio 2005 thì làm sao nhỉ? Giúp mình với, đang cần gấp. hu hu hu

Khi mình chạy với số cạnh 12 thì để cả ngày nó cũng k chạy xong T_T
Admin làm lun cái khử đệ quy cho mình kham khảo với đệ quy chạy lâu quá

Bạn xem cách khử đệ quy trong bài toán Tìm mọi đường đi từ đỉnh D đến C nhé.