Cho đồ thị vô hướng G=(V,E) hãy đếm số thành phần liên thông của đồ thị G.
Ý tưởng thuật toán:
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 đỉ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 kết thúc thuật toán, ngược lại quay về Bước 1.
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 Bai1.inp
- 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: xuất ra màn hình số thành phần liên thông của đồ thị.
Ví dụ:
[ Cài đặt bài toán - 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);
}
//ham tra ve so thanh phan lien thong cua do thi
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++) //khoi tao cac dinh chua danh dau
DanhDau[i] = 0;
do {
j = 0;
while(DanhDau[j]==1) //tim 1 dinh chua duoc danh dau
j++;
DanhDau[j] = 1; //danh dau dinh tim duoc
Dem++; //tang so dinh danh dau len 1
MLT++; //tang so thanh phan lien thong len 1
do {
ThanhCong =0;
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;
Dem++;
if(Dem == n) return MLT;
}
}while (ThanhCong == 1);
} while(Dem<n); //lap lai khi con dinh chua duoc danh dau
return MLT;
}
//chuong trinh chinh
void main() {
clrscr();
int **A,n;
Doc_File(A,n);
cout<<"\nTHANH PHAN LIEN THONG: "<<TPLien_Thong(A,n);
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)
Chúc các bạn thành công!
[tham khảo ĐH Cửu Long]