Search
 
 

Display results as :
 


Rechercher Advanced Search

Latest topics
» NewBlueFx TotalFX Windows-FL | 1.11 GB
Tue Dec 17, 2013 12:42 pm by titquarra

» NewBlueFx TotalFX Windows-FL | 1.11 GB
Tue Dec 17, 2013 12:42 pm by titquarra

» Celebrity.Sex.Tape.UNCUT.&.UNRATED.2012.720p.BRrip.x264.YIFY.mp4
Tue Dec 17, 2013 8:32 am by titquarra

» Maya Autodesk Personal Learning Edition 8.5
Tue Dec 17, 2013 7:47 am by titquarra

» Tuyệt Kỹ Đong Giai Chân Kinh (tuyệt Kỹ cua trai)
Thu Aug 23, 2012 5:38 am by Admin

» Tuyệt kỹ cua giai
Thu Aug 23, 2012 5:36 am by Admin

» NETCAT.........
Mon Aug 13, 2012 6:35 am by Admin

» Bảo mật CSDL bằng phương pháp mã hóa.
Tue Apr 17, 2012 10:04 pm by Admin

» Hàm mã hóa MD5 bằng JavaScript
Tue Apr 17, 2012 10:03 pm by Admin

Shopmotion


Affiliates
free forum


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

View previous topic View next topic Go down

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

Post  Admin on Wed Jun 15, 2011 10:50 pm

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;
}

Admin
Admin

Tổng số bài gửi : 782
Join date : 2009-08-15

View user profile http://hackis.forumotion.com

Back to top Go down

View previous topic View next topic Back to top


 
Permissions in this forum:
You cannot reply to topics in this forum