Thuật Toán Euler - Tìm đường đi Euler Trên đồ Thị G (với đồ Thị Nửa ...

VN SEEDER

Chắc chắn là có đủ....

Menu

• Tin học - Lập trình
  • Lập trình căn bản
  • Lập trình đồ họa
  • Cấu trúc dữ liệu & giải thuật
  • C# và SQL Server
  • Thủ thuật máy tính
• Kiến thức
  • Có thể bạn chưa biết
  • Làm thế nào
  • Nuôi dạy con
  • Sức khỏe
• Đọc
  • Hạt giống tâm hồn
  • Truyện cổ tích
  • Truyện cười
  • Truyện ngụ ngôn
  • Tony buổi sáng
  • Phật học
• Ebook
  • English Ebook
  • Vietnamese Ebook

Trang chủ >> Cấu trúc dữ liệu và giải thuật >> Thuật toán >> Thuật toán Euler - tìm đường đi Euler trên đồ thị G (với đồ thị nửa Euler) Thuật toán Euler - tìm đường đi Euler trên đồ thị G (với đồ thị nửa Euler) Từ khóa Cấu trúc dữ liệu và giải thuật Thuật toán

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 Euler.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ó). [Cài đặt thuật toán với Turbo C++]#include <stdio.h>#include <conio.h>#include <iostream.h>#define Filename "Euler.inp"int Dem = 0, SoCanh=0; //dem so duong di va luu so canh cua do thiint *L; //luu dinh da di quaint **A,n;int XuatPhat=0; //dinh xuat phat la dinh bac le neu do thi co dinh bac le// Doc file chua do thi G (dang ma tran ke)void Doc_File() { int BacDinh; // Bac cua dinh 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; //xuat phat tu dinh bac le (do thi nua Euler) SoCanh+=BacDinh; cout<<endl;} fclose(f); SoCanh = SoCanh/2; //so canh = so dinh chia 2 L = new int [SoCanh+1]; L[0] = XuatPhat;}// In ra duong di Eulervoid InDuongDi() { Dem++; cout<<endl<<XuatPhat+1; for (int i = 1; i<=SoCanh; i++) cout<<" -> "<<L[i]+1;}//thu tuc tim kiem de quyvoid Try(int Canh) { if(Canh > SoCanh) //tim du so canh thi xuat duong di 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; //xoa canh Try(Canh+1); //tim canh tiep theo A[L[Canh-1]][i]=A[i][L[Canh-1]]=1; //phuc hoi canh L[Canh] = 0; } }}// ham chinhvoid main() { Doc_File(); cout<<"\n DUONG DI"; Try(1); if(Dem==0) cout<<"\n KHONG CO"; delete*A,L; getch();}

Bài liên quan

Bài liên quan

>

Thể loại

Cổ tích Có thể bạn chưa biết Nuôi - Dạy con TonyBuổi Sáng-TnBS Sức khỏe Máy tính Lập trình căn bản Làm thế nào Ngẫm Cấu trúc dữ liệu và giải thuật Hạt giống tâm hồn C# và SQL Server Phật học Truyện ngụ ngôn Giáo dục

Ebook Tiếng Anh

CSharp Facebook SEO Windows

Bài xem nhiều

• Lập trình căn bản C: Tìm ước chung lớn nhất, bội chung nhỏ nhất của 2 số a, b
• Lập trình căn bản C: Rút gọn phân số
• Lập trình căn bản C: Xét trúng tuyển thi đại học
• Những lần xê dịch
• Lập trình căn bản C: In ra n số nguyên tố đầu tiên
• Chuyện tiền chuyện bạc (phần 2)
• Lập trình căn bản C: in tam giác số đối đỉnh
• Lập trình căn bản C: tìm số m lớn nhất sao cho tổng từ một đến m nhỏ hơn bằng n
• Làm Menu lựa chọn bằng mũi tên di chuyển lên xuống C/C++
• Đảo ngược số nguyên dương bằng cách sử dụng đệ quy (có trả về kết quả)

top