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
Monday, September 25, 2017

Mô tả bài toán: 
  Cho đồ thị vô hướng G = (V,E) hãy kiểm tra tính liên thông của đồ thị G.

Ý tưởng thuật toán:
  Bước 1: xuất phát từ một đỉnh bất kỳ của đồ thị. Ta đánh dấu đỉnh xuất phát và chuyển sang Bước 2.
  Bước 2: từ một đỉnh i đã đánh dấu, ta đánh dấu đỉnh j nếu A[i,j] = 1 và j chưa được đánh dấu và chuyển sang Bước 3.
  Bước 3: thực hiện Bước 2 cho đến khi không còn thực hiện được nữa chuyển sang Bước 4.
  Bước 4: kiểm tra nếu số đỉnh đánh dấu nhỏ hơn n (hay tồn tại ít nhất một đỉnh chưa được đánh dấu) đồ thị sẽ không liên thông và ngược lại đồ thị liên thông.

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 Input.txt
 - 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: thông báo kết quả ra màn hình ”DO THI LIEN THONG” hay “ DO THI KHONG LIEN THONG”.

Ví dụ:

[Cài đặt: Code Turbo C++]

#include <stdio.h>
#include <conio.h>
#include <iostream.h>


//doc du lieu tu tap tin
void Doc_File(int **A,int &n) {
  FILE*f = fopen("Input.txt","rb");
  fscanf(f,"%d",&n);
  *A = new int [n];
  cout<<"Ma Tran Lien Ket Cua Do Thi";
  for(int i =0;i<n;i++) {
     A[i] = new int [n];
     cout<<endl;
     for(int j =0;j<n;j++) {
        fscanf(f,"%d",&A[i][j]);
        cout<<" "<<A[i][j];
     }
  }
fclose(f);
}

//kiem tra tinh lien thong neu lien thong tra ve gia tri 1 nguoc lai tra ve gia tri 0

char Lien_Thong(int **A,int n) {
  char*DanhDau = new char [n];
  char ThanhCong;
  int Dem=0;
  for(int i = 0; i<n; i++) //Khoi tao moi dinh chua danh dau
     DanhDau[i] = 0;
  DanhDau[0] = 1; //danh dau dinh dau
  Dem++; //dem so dinh duoc danh dau
  do {
     ThanhCong =1; //khong con kha nang loang
      for(i = 0; i<n; i++)
             if(DanhDau[i]==1)
            {
                   for(int j = 0; j<n; j++)
                        if (DanhDau[j] == 0 && A[i][j] > 0)
                        {
                           DanhDau[j] = 1;
                           ThanhCong = 0; //con kha nang loang
                           Dem++;
                           if(Dem == n)
                               return 1;
                         }
             }
   }while (ThanhCong == 0); //lap lai cho den khi khong con kha nang loan
   return 0;
}

//chuong trinh chinh
void main()
{
    clrscr();
    int **A,n;
    Doc_File(A,n);
    if (Lien_Thong(A,n)==1)
       cout<<"\nDO THI LIEN THONG";
    else cout<<"\nDO THI KHONG LIEN THONG";
       delete *A;
    
   getch();
}

/***** LƯU Ý  ****/
- File Input.txt được đặt ở thư mục chứa code [Download file Input.txt tại đây], các bạn có thể tạo phải Input.txt khác tùy vào đồ thị mà bạn muốn kiểm tra
- Download code chương trình tại đây
- Khi download, bạn chờ 5s, click BỎ QUA QUẢNG CÁO (SKIN AD)
- Ngoài phương pháp kiểm tra tính liên thông của đồ thị ở trên, các bạn có thể sử dụng các thuật toán duyệt đồ thị DFS, BFS đề kiểm tra.

Chúc các bạn thành công!


[tham khảo ĐH Cửu Long]

0 comments:

Post a Comment

Popular Posts