BÀI TOÁN
HƯỚNG DẪN THUẬT TOÁN
CHƯƠNG TRÌNH MẪU
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;
}