Gia sư Cần Thơ, Dạy Kèm Cần Thơ

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


Bài 6. Tìm mọi đường đi từ đỉnh D đến C

Share
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 36
Đến từ : Cần Thơ

Bài 6. Tìm mọi đường đi từ đỉnh D đến C

Bài gửi  admin on Sat Dec 19, 2009 12:29 pm

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 thứ hai lưu đỉnh D và đỉnh C.
- Dòng i+2 (0Dữ 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ụ:
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.
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 36
Đến từ : Cần Thơ

Khử đệ quy bài toán tìm mọi đường đi từ thành phố D đến C

Bài gửi  admin on Tue Apr 19, 2011 9:19 am

Code:
#include <stdio.h>
#include <conio.h>
#define max 100
#define FileIn "Input.inp"

int Dem = 0; /*Kiem tra xem co duong di tu C den D hay khong.*/
/*Doc file du lieu cua bai toan luu vao ma tran A.*/
void Doc_File(int A[max][max], int &n, int &D, int &C){
   FILE*f = fopen(FileIn,"rb");
   fscanf(f,"%d%d%d",&n,&D,&C);
   printf("%d %d\n",D,C);
   for(int i =1;i<=n;i++) {
      for(int j =1;j<=n;j++) {
         fscanf(f,"%d",&A[i][j]);
         printf("%3d",A[i][j]);
      }
      printf("\n");
   }
   fclose(f);
}
/*Xuat ket qua tim duoc ra man hinh*/
void XuatDuongDi(int Stack2[max],int DemStack2) {
   printf("%d",Stack2[1]);
   for (int i = 2; i<= DemStack2; i++)
      printf(" -> %d",Stack2[i]);
   printf("\n");
   Dem++;   //tang so duong di len
}
/*Kiem tra dinh i co nam trong Stack2, neu co tra ve ket qua 0 va neu khong co tra ve ket qua 1*/
char KiemTraStack(int i, int Stack2[max],int Dem2){
   for(int j=1;j<=Dem2; j++)
   if(i==Stack2[j])   return 0;
   return 1;
}
/*Xoa tat ca cac phan tu giong nhau o dau Stack1 va Stack2 khi co duong di hoac gap dinh treo khong the di duoc nua*/
void XoaStack(int Stack1[max],int &DemStack1,int Stack2[max],int &DemStack2)
{
   while(Stack1[DemStack1]==Stack2[DemStack2]) {
       DemStack1--;
       DemStack2--;
   }
   DemStack2++;
   Stack2[DemStack2]=Stack1[DemStack1];
}
/*Tim kiem tat ca cac duong di neu co, neu bien Dem>0 thi ton tai duong di va nguoc lai neu Dem=0 thi khong co duong di tu D den C*/
void TimKiem(int A[max][max], int n, int D, int C){
   int Stack1[max],Stack2[max];
   int DemStack1=1,DemStack2=1, DinhTreo;
   int i,ChiSo;

   //Khoi tao 2 stack
   Stack1[DemStack1]=D;
   Stack2[DemStack2]=D;

   while( DemStack1>0 && DemStack2>0 ){
      ChiSo = Stack1[DemStack1];
      DinhTreo = 1; //Gia su ton tai dinh treo

      for(i=1; i<=n; i++)
      if(A[ChiSo][i]==1 && KiemTraStack(i,Stack2,DemStack2)==1){
         DemStack1++;
         Stack1[DemStack1] = i;
         DinhTreo = 0;
      }
      
if(DinhTreo==1)
   XoaStack(Stack1,DemStack1,Stack2,DemStack2);
      else {
         DemStack2++;
         Stack2[DemStack2]=Stack1[DemStack1];
      }
      if(Stack2[DemStack2]==C){
         XuatDuongDi(Stack2,DemStack2);
         XoaStack(Stack1,DemStack1,Stack2,DemStack2);
      }

   }
}

void main() {
   clrscr();
   int A[max][max],n,D,C;
   Doc_File(A,n,D,C);
   TimKiem(A,n,D,C);
if(Dem==0) printf("Khong co duong di tu %d den %d.",D,C);
   getch();
}

    Hôm nay: Mon Nov 20, 2017 4:28 pm