Lập trình CTDL & Thuật toán Lập trình C/C++

Kiểm tra tính liên thông của đồ thị trong lập trình

25 Tháng Hai, 2023

DANH SÁCH BÀI VIẾT
Giải thuật tìm kiếm theo chiều rộng BFS (Breadth-first search)
Giải thuật tìm kiếm theo chiều sâu DFS (Depth First Search)
Duyệt đồ thị, tìm kiếm đường đi dài nhất, đường đi ngắn nhất trong đồ thị
Kiểm tra tính liên thông của đồ thị  trong lập trình

Đồ thị liên thông có nghĩa là từ mọi đỉnh bất kì đều sẽ có đường đi trực tiếp hoặc gián tiếp tới các đỉnh còn lại, ngược lại gọi là đồ thị không liên thông.

Kiểm tra đồ thị liên thông

Mình có 2 đồ thị minh họa sau:

Ví dụ 1: Với đồ thị này là đồ thị liên thông vì tất cả cảnh đỉnh đều tồn tại đường đi trực tiếp hoặc gián tiếp với nhau.

Ta có ma trận cho đồ thị này sẽ là:

Ví dụ 2: Đồ thị này là không liên thông, và nó chia thành 2 đồ thị con liên thông là (1,2) và (3,4).

Ta có ma trận cho đồ thị này sẽ là:

Vậy ý tưởng làm sao để kiểm tra được đồ thị liên thông, và nếu không liên thông thì sẽ có bao nhiêu đồ thị con liên thông?

Rất đơn giản, xuất phát từ một đỉnh bất kì ta sử dụng giải thuật DFS hoặc BFS để duyệt qua từng đỉnh của đồ thị, đỉnh nào được duyệt qua ta đánh dấu là đã được duyệt. Sau khi chạy hết đoạn chương trình nếu như tất cả các đỉnh đều duyệt qua được tức là đồ thị liên thông, ngược lại nếu sót 1 hoặc nhiều hơn số đỉnh không được duyệt thì đồ thị không liên thông.

Trường hợp đồ thị không liên thông ta muốn đếm số lượng đồ thị con liên thông, sau khi kết thúc đoạn chương trình duyệt ta sẽ tiếp tục xét xem còn đỉnh nào chưa được duyệt thì thực hiện gọi lại hàm duyệt bắt đầu từ đỉnh đó mỗi lần như vậy là một đồ thị con liên thông, thực hiện lặp cho đến khi không còn đỉnh nào.

Vậy ta viết chương trình như sau:

#include <iostream>
#include <algorithm>
using namespace std;
bool dd[1000]; //Mảng đánh dấu đỉnh
int dem=1, dem2=1; //Đếm để đếm số đỉnh, đếm 2 để đếm số đồ thị con liên thông nếu có
void BFS(int a[][1000], int n, int i)
{
	dd[i]=1; //Đánh dấu đỉnh được duyệt
	for(int j=0;j<n;j++)
	{
		if(a[i][j] != 0 && dd[j]==0)//Nếu 2 đỉnh có đường đi và đỉnh chưa được duyệt qua
		{
			dem++;//Đếm đỉnh được duyệt qua
			BFS(a,n,j); //Đệ quy với đỉnh j
		}
	}
}
int main()
{
	int n; cout<<"nhap so dinh: "; cin>>n;
	int a[n][1000];
	cout<<"Nhap ma tran do thi: \n";
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			 cin>>a[i][j];
 	
	BFS(a,n,0);  //Gọi hàm duyệt đồ thị
	if(dem==n) cout<<"do thi lien thong"; //Nếu trong 1 lần duyệt có thể đi qua hết các đỉnh thì đồ thị là liên thông
	
	else{
		for(int i=1;i<n;i++)
		{
			if(dd[i] == 0) //Kiểm tra đỉnh đó chưa được duyệt
			{
				BFS(a,n,i); cout<<endl; //Gọi hàm duyệt bắt đầu từ đỉnh chưa được duyệt
				dem2++;//Đếm đồ thị con
			}
		}
		cout<<"Do thi khong lien thong";
		cout<<"\n So do thi con lien thong "<<dem2;
	}
}

Kết quả thực hiện chương trình với 2 ví dụ trên:

Kết quả ví dụ 1