Bài 14. Bài toán tìm mọi đường đi của đồ thị G với đỉnh đầu là D và đỉnh cuối là C

Có n thành phố biết rằng đường đi giữa hai các thành phố (nếu có) là đường đi hai chiều. Sơ đồ mạng lưới giao thông của n thành phố cho bởi ma trận Anxn trong đó:
a. A[i,j] = 1 nếu có đường đi từ thành phố i đến thành phố j.
b. A[i,j] = 0 nếu không có đường đi từ thành phố i đến thành phố j.
c. A[i,j] = A[j,i].
Hãy xác định mọi đường từ thành phố D đến thành phố C (nếu có).
Dữ liệu vào: cho trong file Bai4.inp.
- Dòng đầu ghi số n là số đỉnh của một đồ thị (0- Dòng thứ hai lưu đỉnh D và đỉnh C.
- Dòng i+2 ( ) 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: Xuất ra màn hình mọi đường đi từ đỉnh D đến C hay thông báo không tồn tại đường đi từ D đến C.
Ví dụ:

BAI4.INP
5
1 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
1->2->3->4->5
1->2->4->5
1->5

HƯỚNG DẪN THUẬT TOÁN
Sử dụng kỹ thuật tìm kiếm theo chiều sâu.
HƯỚNG DẪN CÀI ĐẶT
Sử dụng kỹ thuật cài đặt tìm kiếm theo phương pháp đệ quy.
- Các biến lưu trữ phải khai báo toàn cục, các biến lặp phải khai báo cục bộ.
- Trong thủ tục khởi tạo (void KhoiTao): khởi tạo mọi đỉnh chưa được đánh dấu, quá trình tìm kiếm xuất phát từ đỉnh D nên đánh dấu đỉnh D và lưu trữ đường đi xuất phát từ đỉnh D.
- Trong thủ tục tìm kiếm (void TimKiem): ta xuất phát tìm kiếm đỉnh tiếp theo dựa trên đỉnh lưu trữ trước đó để đảm bảo có đường đi (thoả tính liền kề của đồ thị). Nếu thoả mãn điều kiện đỉnh tìm kiếm trước đó bằng đỉnh C ta tiến hành xuất đường đi (đây là điều kiện đệ quy).

CHƯƠNG TRÌNH MẪU

Code:

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define FileIn "Bai4.inp"
int Dem = 0;      //Đếm số đường đi
int*L;         //Lưu lại đường đã đi
char*DanhDau;   //Đánh dấu đỉnh đã đi
int **A,n,D,C;
/*Dọc file dữ liệu theo yêu cầu của chương trình*/
void Doc_File(){
   FILE*f = fopen(FileIn,"rb");
   fscanf(f,"%d%d%d",&n,&D,&C);      //Đọc số đỉnh n,  đỉnh D và C
   cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<D<<" "<<C<<endl;
   *A = new int [n];
   for(int i =0;i<n;i++) {
      A[i] = new int [n];
      for(int j =0;j<n;j++) {
         fscanf(f,"%d",&A[i][j]);
         cout<<A[i][j]<<" ";
      }
      cout<<endl;
   }
   fclose(f);
   D--;      //Giảm D và C vì ta xử lý số đỉnh từ 0 đến n-1
   C--;
}
/*Khởi tạo các tham số ban đầu cho chương trình*/
void KhoiTao() {
   DanhDau = new char [n];
   L = new int [n];
   for (int i = 0; i<n; i++) {   //Tất cả các đỉnh chưa được đánh dấu
      DanhDau[i] = 0;
      L[i] = 0;
   }
   DanhDau[D] = 1;      //Đánh dấu đỉnh đầu tiên
   L[0] = D;         //Lưu lại đỉnh đầu tiên là đỉnh xuất phát
}
void InDuongDi(int SoCanh) {
   Dem++;
   cout<<endl<<D+1;
   for (int i = 1; i<SoCanh; i++)
      cout<<" -> "<<L[i]+1;
}
/*Thủ tục đệ quy tìm kiếm đường đi*/
void TimKiem(int SoCanh) {
   if(L[SoCanh-1] == C)     //Xuất nếu đỉnh tìm từ lần tìm kiếm trước bằng C
    InDuongDi(SoCanh);
   else {   
    for(int i = 0; i<n; i++)
      if( A[L[SoCanh-1]][i]>0 && DanhDau[i] == 0 ){
         L[SoCanh] = i;      //Lưu lại đỉnh đi qua
         DanhDau[i] = 1;      //Đánh dấu đỉnh đi qua
         TimKiem(SoCanh+1);   //Tìm kiếm đỉnh tiếp theo
         L[SoCanh] = 0;      
         DanhDau[i] = 0;      //Phục hồi đỉnh đỉnh đã đi qua
      }
   }
}
/*Chương trình chính*/
void main() {
   Doc_File();   KhoiTao();
   cout<<"Duong di tu "<<D+1<<" den "<<C+1;
   TimKiem(1);
   if(Dem==0)      cout<<" khong co";
   delete*A,DanhDau,L;
   getch();
}


----------------------------
Cuộc sống là thử thách

Được sửa bởi Admin ngày Fri Jun 10, 2011 12:45 pm; sửa lần 4.

Một bài toán khá mẫu mực. Giải bằng đệ quy cũng khá hay. Tuy nhiên, nếu có thể thì cũng nên Post lên những giải thuật chính thống luôn tiện để sinh viên có cơ hội so sánh đối chiếu. Việc dùng đệ quy để giải các bài toán về mảng hai chiều trở lên thì dữ liệu bị hạn chế rất nhiêu. Cụ thể ở bài này nếu là đồ thị đầy đủ vuông cấp 20 trở lên thì cũng hơi rối.