Mô tả bài toán: 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ố đỉ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:
Từ khóa: c, c++, toán rời rạc, liên thông, đồ thị, kỹ thuật lập trình, giải thuật, đếm thành phần liên thông của đồ thị
C - C Plus Plus
Cấu trúc Dữ liệu - Giải thuật
Kỹ thuật lập trình
Code C/C++: Đếm số thành phần liên thông của đồ thị
Subscribe to:
Post Comments (Atom)
Nhãn liên kết
An toàn thông tin
Android
ASP.NET
C - C Plus Plus
C#
Cài đặt - Cấu hình
Cấu trúc Dữ liệu - Giải thuật
Chữ ký số
CodeIgniter
Đồ họa máy tính
Hệ điều hành mã nguồn mở
HTML/CSS
iOS
Java
JavaScript
Kinh nghiệm
Kỹ thuật đồ họa
Kỹ thuật lập trình
Lập trình căn bản
Lập trình hướng đối tượng
Lập trình mạng
Lập trình Mobile
Lập trình Shell
Mật mã học
Microsoft Technology
MS Access
MySQL
Pascal
PHP
PHP Framework
SQL Server
Test
Thiết kế Website
Toán cao cấp
Ubuntu/Fedora/RedHat
VB-VB.NET
Visual Studio 2015
Visual Studio 2017
Windows Form
Windows Phone
