Đườ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();
}