Header Ads Widget

Ticker

6/recent/ticker-posts

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

Đăng nhận xét