Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy xác định mọi đường đi qua tất cả các cạnh mỗi cạnh chỉ qua duy nhất 1 lần.
Ý tưởng thuật toán:sử dụng kỹ thuật tìm kiếm theo chiều sâu bằng cách xóa cạnh đã đi qua trong quá trình tìm kiếm đường đi.
Mô tả dữ liệu đầu vào và đầu ra của bài toán:
Dữ liệu vào: cho trong tập tin Bai5.inp
- Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100)
- Dòng i+1 (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: in ra màn hình đường đi qua tất cả các cạnh (nếu có)
Ví dụ:
Cài đặt chương trình:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define Filename "Bai5.inp"
int Dem = 0, SoCanh=0;
int *L;
int **A,n;
int XuatPhat=0;
void Doc_File() {
int BacDinh;
FILE*f = fopen(Filename,"rb");
fscanf(f,"%d",&n);
cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<n<<endl;
*A = new int [n];
for(int i =0;i<n;i++) {
A[i] = new int [n];
BacDinh = 0;
for(int j =0;j<n;j++) {
fscanf(f,"%d",&A[i][j]);
cout<<A[i][j]<<" ";
if(A[i][j] == 1)
BacDinh++;
}
if(BacDinh%2==1)
XuatPhat = i;
SoCanh+=BacDinh;
cout<<endl;
}
fclose(f);
SoCanh = SoCanh/2;
L = new int [SoCanh+1];
L[0] = XuatPhat;
}
void InDuongDi() {
Dem++;
cout<<endl<<XuatPhat+1;
for (int i = 1; i<=SoCanh; i++)
cout<<" -> "<<L[i]+1;
}
void Try(int Canh) {
if(Canh > SoCanh)
InDuongDi();
else {
for(int i = 0; i<n; i++)
if( A[L[Canh-1]][i]>0){
L[Canh] = i;
A[L[Canh-1]][i]=A[i][L[Canh-1]]=0;
Try(Canh+1);
A[L[Canh-1]][i]=A[i][L[Canh-1]]=1;
L[Canh] = 0;
}
}
}
void main() {
Doc_File();
cout<<"\nDUONG DI";
Try(1);
if(Dem==0)
cout<<" KHONG CO";
delete*A,L;
getch();
}
Kết quả chạy chương trình:
Tags: Kỹ thuật lập trình, toán rời rạc, c, c++, euler, đồ thị, tìm đường đi
C - C Plus Plus
Cấu trúc Dữ liệu - Giải thuật
Kỹ thuật lập trình
Code C/C++: Tìm đường đi Euler của đồ thị (bài toán tìm đường đi)
Subscribe to:
Post Comments (Atom)
Nhãn liên kết
An toàn thông tin
Android
ASP.NET
C - C Plus Plus
C#
Cài đặt - Cấu hình
Cấu trúc Dữ liệu - Giải thuật
Chữ ký số
CodeIgniter
Đồ họa máy tính
Hệ điều hành mã nguồn mở
HTML/CSS
iOS
Java
JavaScript
Kinh nghiệm
Kỹ thuật đồ họa
Kỹ thuật lập trình
Lập trình căn bản
Lập trình hướng đối tượng
Lập trình mạng
Lập trình Mobile
Lập trình Shell
Mật mã học
Microsoft Technology
MS Access
MySQL
Pascal
PHP
PHP Framework
SQL Server
Test
Thiết kế Website
Toán cao cấp
Ubuntu/Fedora/RedHat
VB-VB.NET
Visual Studio 2015
Visual Studio 2017
Windows Form
Windows Phone
