Cài đặt Thuật Toán Duyệt đồ Thị - DFS, BFS - VN SEEDER

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 >> Cài đặt thuật toán duyệt đồ thị - DFS, BFS Cài đặt thuật toán duyệt đồ thị - DFS, BFS Từ khóa Cấu trúc dữ liệu và giải thuật Thuật toán

Cài đặt thuật toán duyệt đồ thị - DFS, BFS trong lý thuyết đồ thịYêu cầu: - Đọc file "D:\\G.txt" chứa ma trận kề biểu diễn đơn đồ thị vô hướng G, có dạng sau:Ví dụ:40 1 0 11 0 1 10 1 0 01 1 0 0 Trong đó: + Dòng đầu tiên là số đỉnh + Các dòng còn lại biểu diễn ma trận kề của đồ thị G- In ma trân kề vừa đọc được- Duyệt đồ thị với thuật toán DFS, BFS. In kết qua ra màn hình- Đếm số thành phần liên thông- Kiểm tra xem đồ thị có phải là Euler không ?Code [ Dev - C++ ]:#include <iostream>#include <stdio.h>#include <conio.h>#include <values.h>#define max 100#define FileIn "D:\\G.txt"using namespace std;int chuaXet[max];// A: ma tran ke cua G, n: so dinhint A[max][max],n; // doc file chua do thi G luu vao ma tran Avoid Doc_File(int A[max][max], int &n) { FILE *f = fopen(FileIn,"rb"); fscanf(f,"%d",&n); cout<<"\n So dinh: "<<n<<"\n Ma tran ke: "<<endl; for(int i =0;i<n;i++) { for(int j =0;j<n;j++) { fscanf(f,"%d",&A[i][j]); cout<<A[i][j]<<" ";}cout<<endl;}fclose(f); }// Khoi tao chua xetvoid KhoiTao_ChuaXet(){ for (int i=0;i<max;i++) chuaXet[i]=1; }// thuat toan DFSvoid DFS(int u){// xet dinh u chuaXet[u]=0; cout<<u<<"->"; for(int v=0;v<n;v++) if(chuaXet[v]==1&&A[u][v]==1) { DFS(v); } }// thuat toan BFSvoid BFS(int u){ int queue[max], dau=0,cuoi=0; for(int i=0;i<max;i++) queue[i]=0; queue[cuoi]=u; chuaXet[u]=0; cout<<u<<"->"; while(dau>=cuoi) { int p=queue[cuoi]; cuoi++; for(int v=0;v<n;v++) if(chuaXet[v]==1&&A[p][v]==1) { dau++; queue[dau]=v; chuaXet[v] =0; cout<<v<<"->"; } }}// Kiem tra chuaXetint KT_ChuaXet(){ for (int i=0;i<n;i++) if (chuaXet[i]==1) return i;return -1;}// Dem so thanh phan lien thongint DemSLT(){ int slt=0; KhoiTao_ChuaXet(); while (KT_ChuaXet()!=-1) { int i=KT_ChuaXet(); DFS(i); slt++; } cout<<"\n So lien thong: "<<slt;return slt;}// tim bac cac dinh int Deg(int i){ int deg=0; for(int j=0;j<n;j++) { deg +=A[i][j]; } return deg; }// Kiem tra do thi Eulervoid Test_Euler(){ if (DemSLT()==1){ // tim bac cua do thi int soDinhLe=0; for (int i=0;i<n;i++) if(Deg(i)%2!=0) soDinhLe++; if (soDinhLe==0) cout<<"\n Do thi la Euler"; else if (soDinhLe==2) cout<<"\n Do thi la nua Euler"; else cout<<"\n Do thi khong phai Euler"; }else cout<<"\n Do thi khong la Euler";}// ham chinhint main() { // doc ma tran Doc_File(A,n); // Duyet do thi DFS KhoiTao_ChuaXet(); cout<<"\n Duyet do thi DFS: "; DFS(0); // Duyet do thi BFS KhoiTao_ChuaXet(); cout<<"\n Duyet do thi BFS: "; BFS(0); // Dem so lien thong DemSLT(); // Kiem tra Euler Test_Euler();return 0;}--------------------------Kế quả:So dinh: 4Ma tran ke:0 1 0 11 0 1 10 1 0 01 1 0 0Duyet do thi DFS: 0->1->2->3->Duyet do thi BFS: 0->1->3->2->--------------------------------

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