Thuật toán kiểm tra tính liên thông của đồ thị

Đề: Cho một giả đồ thị vô hướng G = (V, E) có N đỉnh. Hãy viết chương trình kiểm tra

xem G có liên thông hay không.

Input:

- Tên file: “lienthong.inp”

- Trong file này, dòng đầu tiên là số N, N dòng tiếp theo là ma trận kề cấp N.

Output: in kết quả ra màn hình và ra file “lienthong.out”.

Ý 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.

1. #include<iostream>
2. #include<fstream>
3. using namespace std;
4.  
5. bool xet_tinh_lien_thong(int arr[][100], int n);
6.  
7.  
8. int main()
9. {
10. ifstream file_in("lienthong.inp", ios_base::in);
11. ofstream file_out("lienthong.out", ios_base::out);
12.  
13. int arr[100][100];
14. int n;
15. file_in >> n; // doc n
16.  
17. for(int i =0;i<n;i++) // doc mang
18. {
19. for(int j=0;j<n;j++)
20. {
21. file_in >> arr[i][j];
22. }
23. }
24.  
25. // xuat mang
26. cout<<n<<endl;
27. for(int i =0;i<n;i++)
28. {
29. for(int j=0;j<n;j++)
30. {
31. cout<<arr[i][j]<< " ";
32. }
33. cout<<endl;
34. }
35. if(xet_tinh_lien_thong(arr,n))
36. {
37. cout<<"Day la do thi lien thong";
38. file_out << "Day la do thi lien thong";
39. }
40. else
41. {
42. cout<<"Day la do thi khong lien thong";
43. file_out << "Day la do thi khong lien thong";
44. }
45. return 0;
46. }
47.  
48. bool xet_tinh_lien_thong(int arr[][100], int n)
49. {
50. int danh_dau[n];
51.  
52. danh_dau[0] = 1; // danh dau gia tri dau tien la 1
53. int dem_so_dinh_duoc_danh_dau = 1;
54.  
55.  
56. for(int i=1;i<n;i++)
57. {
58. danh_dau[i] = 0; // khoi tao gia tri cho cac bien danh_dau = 0;
59. }
60.  
61. for(int i =0; i<n;i++)
62. {
63. for(int j=0;j<n;j++)
64. {
65. if(arr[i][j] == 1 && danh_dau[j] == 0 ) // neu arr[i][j] == 1 va dinh j chua dc danh dau thi danh dau dinh do
66. {
67. danh_dau[j] = 1;
68. dem_so_dinh_duoc_danh_dau++;
69. }
70. }
71. }
72. cout<<"so dinh dc danh dau = "<<dem_so_dinh_duoc_danh_dau<<endl;
73. if(dem_so_dinh_duoc_danh_dau == n)
74. {
75. return true;
76. }
77. else
78. {
79. return false;
80. }
81. }

Download Code