Tìm mọi đường đi từ đỉnh D đến 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 Bai2.inp.
- Dòng đầu ghi số n là số đỉnh của một đồ thị (0
- Dòng i+2 (0
Ví dụ:
Input 1:
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:
1->2->3->4->5
1->2->4->5
1->5
Input 2:
6
1 4
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
0 0 0 0 1 1
0 0 0 1 0 1
0 0 0 1 1 0
Output 2:
KHONG CO DUONG DI
Input 3:
5
1 5
0 1 0 1 1
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
1 1 0 1 0
Output 3:
1->2->3->4->5
1->2->5
1->4->3->2->5
1->4->5
1->5
HƯỚNG DẪN THUẬT TOÁN
Sử dụng thuật toán 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).
Code:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define FileIn "Bai2.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();
}
Được sửa bởi Admin ngày Thu May 26, 2011 8:35 am; sửa lần 1.