Search
 
 

Display results as :
 


Rechercher Advanced Search

Latest topics
» NewBlueFx TotalFX Windows-FL | 1.11 GB
Tue Dec 17, 2013 12:42 pm by titquarra

» NewBlueFx TotalFX Windows-FL | 1.11 GB
Tue Dec 17, 2013 12:42 pm by titquarra

» Celebrity.Sex.Tape.UNCUT.&.UNRATED.2012.720p.BRrip.x264.YIFY.mp4
Tue Dec 17, 2013 8:32 am by titquarra

» Maya Autodesk Personal Learning Edition 8.5
Tue Dec 17, 2013 7:47 am by titquarra

» Tuyệt Kỹ Đong Giai Chân Kinh (tuyệt Kỹ cua trai)
Thu Aug 23, 2012 5:38 am by Admin

» Tuyệt kỹ cua giai
Thu Aug 23, 2012 5:36 am by Admin

» NETCAT.........
Mon Aug 13, 2012 6:35 am by Admin

» Bảo mật CSDL bằng phương pháp mã hóa.
Tue Apr 17, 2012 10:04 pm by Admin

» Hàm mã hóa MD5 bằng JavaScript
Tue Apr 17, 2012 10:03 pm by Admin

Shopmotion


Affiliates
free forum


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

View previous topic View next topic Go down

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

Post  Admin on Wed Jun 15, 2011 10:45 pm

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>
#include <values.h>
#define FileInt "Bai8.inp"
#define FileOut "Bai8.out"

/*Lưu lại những cạnh đã đi qua x->y*/
typedef struct Egde {
  int x,y;
};
/*Doc dữ liệu từ file*/
void Doc_File(int **A,int &n){
  FILE*f = fopen(FileInt,"rb");
  fscanf(f,"%d",&n);
  *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]);
      }
  }
  fclose(f);
}
/*Ghi dữ liệu ra file*/
void Ghi_File(Egde*L,int n,int Sum) {
  FILE*f = fopen(FileOut,"wb");
  fprintf(f,"%d\n",Sum);
  for(int i =0; i<n-1; i++)
      fprintf(f,"%d - %d\n",L[i].x+1,L[i].y+1);
  fclose(f);
}
/*Thuật toán Kruskal  */
void Kruskal(int **A, int n){
  char *D = new char[n];
  Egde *L = new Egde[n-1];
  int min, Dem = 0, Sum = 0, T = 0, Temp;
  for(int i=0; i<n; i++)
      D[i] = 0; 
  do{
      min = MAXINT;
      for( i=0; i<n; i++)
      for(int j=0; j<n; j++)
      if(A[i][j]>0 && min>A[i][j]&& !(D[i]!=0 && D[i]==D[j])) {
            min = A[i][j];
            L[Dem].x = i;
            L[Dem].y = j;
      }
      /*Tạo ra cây mới*/
      if(D[L[Dem].x] ==0 && D[L[Dem].y] == 0){
        T++;
        D[L[Dem].x] = D[L[Dem].y] = T;
      }
      /*Đưa đỉnh tương ứng vào cây*/
      if(D[L[Dem].x] == 0 && D[L[Dem].y] != 0)
        D[L[Dem].x] = D[L[Dem].y];
      /*Đưa đỉnh tương ứng vào cây*/
      if(D[L[Dem].x] != 0 && D[L[Dem].y] == 0)
        D[L[Dem].y] = D[L[Dem].x];
      /*Ghép 2 cây thành 1 cây mới*/
      if(D[L[Dem].x] != D[L[Dem].y] && D[L[Dem].y]!=0)  {
        Temp = D[L[Dem].x];
        for( i=0; i<n; i++)
        if(Temp==D[i])
            D[i]=D[L[Dem].y];
      }
      Sum+=min;
      Dem++;
  } while(Dem<n-1);
  Ghi_File(L,n,Sum);
}
/*Chương trình chính*/
void main() {
  int **A,n;
  Doc_File(A,n);
  Kruskal(A,n);
  delete *A;
}

Admin
Admin

Tổng số bài gửi : 782
Join date : 2009-08-15

View user profile http://hackis.forumotion.com

Back to top Go down

View previous topic View next topic Back to top


 
Permissions in this forum:
You cannot reply to topics in this forum