Xét tính liên thông của đồ thị
Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy kiểm tra tính liên thông của đồ thị G.
Ý tưởng thuật toán:
Bước 1: xuất phát từ một đỉnh bất kỳ của đồ thị. Ta đánh dấu đỉnh xuất phát 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: kiểm tra nếu số đỉnh đánh dấu nhỏ hơn n (hay tồn tại ít nhất một đỉnh chưa được
đánh dấu) đồ thị sẽ không liên thông và ngược lại đồ thị liên thông.
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: thông báo kết quả ra màn hình ”DO THI LIEN THONG” hay “ DO THI KHONG LIEN THONG”.
Cài đặt chương trình:
#include<math.h>
#include<iostream>
#include<conio.h>
#include<stdio.h>
#define tenfile "bai1.txt"
using namespace std;
//Hàm đọc file
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);
}
//kiem tra tinh lien thong neu lien thong tra ve gia tri 1 nguoc lai tra ve gia tri 0
char Lien_Thong(int **A,int n){
char *DanhDau = new char [n];
char ThanhCong;
int Dem=0;
for(int i = 0; i<n; i++) //Khoi tao moi dinh chua danh dau
DanhDau[i] = 0;
DanhDau[0] = 1; //danh dau dinh dau
Dem++; //dem so dinh duoc danh dau
do {
ThanhCong =1; //khong con kha nang loang
for(int i = 0; i<n; i++)
if(DanhDau[i]==1){
for(int j = 0; j<n; j++)
if (DanhDau[j] == 0 && A[i][j] > 0){
DanhDau[j] = 1;
ThanhCong = 0; //con kha nang loang
Dem++;
if(Dem == n)
return 1;
}
}
}while (ThanhCong == 0); //lap lai cho den khi khong con kha nang loan
return 0;
}
//Chuong trinh chinh
int main(){
int **A,n;
Doc_File(A,n);
if (Lien_Thong(A,n)==1)
cout<<"\nDO THI LIEN THONG";
else
cout<<"\nDO THI KHONG LIEN THONG";
delete *A;
getch();
return 0;
}
Kết quả chạy chương trình:
Từ khóa: Đồ thị, liên thông, graphics, toán rời rạc, kỹ thuật lập trình, c, c++
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++: Xét tính 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
