Ý 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ố đỉ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 Bai2.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 chương trình:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define TenFile "Bai2.inp"
//Đọc dữ liệu từ file Bai2.inp
void Doc_File(int **A,int &n) {
FILE*f = fopen(TenFile,"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);
}
//Hàm trả về số thành phần liên thông của đồ thị
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++)
DanhDau[i] = 0;
do {
j = 0;
while(DanhDau[j]==1)
j++;
DanhDau[j] = 1;
Dem++;
MLT++;
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);
return MLT;
}
//Chương trình chính
void main(){
clrscr();
int **A,n;
Doc_File(A,n);
cout<<"\nThanh phan lien thong: "<<TPLien_Thong(A,n);
delete *A;
getch();
}
Kết quả chạy chương trình:
