Gia sư Cần Thơ, Dạy Kèm Cần Thơ

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


Bài 10. Đếm số thành phần liên thông của đồ thị vô hướng G

Share
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 36
Đến từ : Cần Thơ

Bài 10. Đếm số thành phần liên thông của đồ thị vô hướng G

Bài gửi  admin on Thu May 26, 2011 8:50 am

BÀI TOÁN
Viết chương trình đếm số thành phần liên thông của đồ thị vô hướng Anxn với:
- A[i,j] = 1 nếu có đường đi từ i đến j, A[i,j] = 0 nếu không có đường đi từ i đến j.
- A[i,j] = A[j,i].
Dữ liệu vào: cho trong file Bai2.inp nội dung dữ liệu giống dữ liệu Bài Toán 2.
Dữ liệu ra: hiển thị số thành phần liên thông của đồ thị ra màn hình.
Ví dụ:
BAI3.INP
6
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
0 0 0 0 1 1
0 0 0 1 0 1
0 0 0 1 1 0
MIEN LIEN THONG: 2

BAI3.INP
5
0 0 0 0 1
0 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
MIEN LIEN THONG: 1
HƯỚNG DẪN THUẬT TOÁN
Ý tưởng: Sử dụng thuật toán loang giống như bài toán 2.
Bước 0: Khởi tạo số thành phần liên thông bằng 0.
Bước 1: Xuất phát từ một đỉnh chưa được đánh dấu của đồ thị. Ta đánh dấu đỉnh xuất phát, tăng số thành phần liên thông lên 1 và chuyển sang bước 2.
Bước 2: Từ một đỉnh i đã đánh dấu, ta đánh dấu tất cả các đỉ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: Nếu số số đỉnh đánh dấu bằng n (mọi đỉnh đều được đánh dấu) kết thúc thuật toán và trả về số thành phần liên thông, ngược lại quay về bước 1.
Chú ý: Nếu số thành phần liên thông bằng 1 đồ thị liên thông.
CHƯƠNG TRÌNH MẪU
Code:
/*Hàm trả về số thành phần liên thông của đồ thị vô hướng */
int TPLien_Thong(int **A, int n) {
   char*DanhDau = new char [n];
   char ThanhCong;
   int Dem=0, i,j, MLT=0;
   for( i = 0; i<n; i++)         //Khởi tạo mọi đỉnh chưa được đánh dấu
      DanhDau[i] = 0;
   do {   
    j = 0;
      while(DanhDau[j]==1)   //B1: Tìm 1 đỉnh chưa được đánh dấu
         j++;
      DanhDau[j] = 1;      //Đánh dấu đỉnh tìm được
      Dem++;         //Tăng số đỉnh được đánh dấu lên 1
      MLT++;         //Tăng miền liên thông lên 1
      do {
         ThanhCong =0;   //Giả sử không còn khả năng loang
         for(i = 0; i<n; i++)
         if(DanhDau[i]==1)
            for(j = 0; j<n; j++)
            if (DanhDau[j] == 0 && A[i][j] > 0) {
               DanhDau[j] = 1;
               ThanhCong =1;   //Còn khả năng loang
               Dem++;
               if(Dem == n) return MLT;
            }
      }while (ThanhCong == 1);   //Lặp khi còn khả năng loang
   } while(Dem<n);         //Lặp khi còn tồn tại đỉnh chưa được dánh dấu
   return MLT;
}

    Hôm nay: Mon Nov 20, 2017 4:32 pm