Code C/C++: Tìm mọi đường đi từ giữa hai đỉnh của đồ thị

Tìm mọi đường đi từ giữa hai đỉnh
Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy xác định mọi đường đi từ đỉnh D tới đỉnh C của đồ thị G.
Ý tưởng thuật toán: sử dụng kỹ thuật tìm kiếm theo chiều sâu.
Mô tả dữ liệu đầu vào và đầu ra của bài toán:
Dữ liệu vào: đồ thị liên thông và cho trong tập tin Bai3.inp 
-  Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100)
-  Dòng thứ hai lưu đỉnh D và đỉnh C.
-  Dòng i+2 (1<=i<=n) 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.
Mô tả:

Cài đặt chương trình:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define FileIn "Bai1a.inp"
intDem = 0;    
int *L;     
char  *DanhDau; 
int **A,n,D,C;
//Đọc dữ liệu từ tập tin
void Doc_File()
FILE*f = fopen(FileIn,"rb");
fscanf(f,"%d%d%d",&n,&D,&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--; 
C--;
}
//Khởi tạo các biến ban đầu
void KhoiTao() {
DanhDau = new char [n];
L = new int [n];
for (int i = 0; i<n; i++) {
DanhDau[i] = 0;
L[i] = 0;
}
DanhDau[D] = 1;    
L[0] = D;      
}
void InDuongDi(int SoCanh) {
Dem++;
cout<<endl<<D+1;
for (int i = 1; i<SoCanh; i++)
cout<<" -> "<<L[i]+1;
}
void Try(int SoCanh) {
if(L[SoCanh-1] == C)    
InDuongDi(SoCanh);
else {
for(int i = 0; i<n; i++)
if( A[L[SoCanh-1]][i]>0 && DanhDau[i] == 0 ){
L[SoCanh] = i;  
DanhDau[i] = 1; 
Try(SoCanh+1); 
L[SoCanh] = 0;
DanhDau[i]= 0;  
}
}
}
void main() {
Doc_File();
KhoiTao();
cout<<"Duong di tu "<<D+1<<" den "<<C+1;
Try(1);
if(Dem==0)
cout<<" khong co duong di";
delete*A,DanhDau,L;
getch();

}
Kết quả chạy chương trình:

Từ khóa: đường đi, đồ thị, đỉnh, c, c++, kỹ thuật lập trình, toán rời rạc, liên thông, tìm đường đi giữa 2 đỉnh của đồ thị

Related Posts
Previous
« Prev Post