Kênh Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
kiem tien, kiem tien online, kiem tien truc tuyen, kiem tien tren mang
Tuesday, September 26, 2017

 Cài đặt thuật toán duyệt đồ thị - DFS, BFS trong lý thuyết đồ thị

http://adf.ly/e5LU6

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ụ:
4
0 1 0 1
1 0 1 1
0 1 0 0
1 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 dinh
int A[max][max],n;

// doc file chua do thi G luu vao ma tran A


void 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 xet
void KhoiTao_ChuaXet(){
  for (int i=0;i<max;i++)
   chuaXet[i]=1;
 }

// thuat toan DFS
void 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 BFS

void 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 chuaXet
int KT_ChuaXet(){
  for (int i=0;i<n;i++)
     if (chuaXet[i]==1) return i;
return -1;
}


// Dem so thanh phan lien thong

int 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 Euler

void 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 chinh

int 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: 4
Ma tran ke:
0 1 0 1
1 0 1 1
0 1 0 0
1 1 0 0

Duyet do thi DFS: 0->1->2->3->
Duyet do thi BFS: 0->1->3->2->
--------------------------------

[Download Code tại đây]

http://laptrinhmaytinh.net
Next
This is the most recent post.
Previous
Older Post

0 comments:

Post a Comment

Popular Posts