Kiểm tra tính liên thông của đồ thị vô hướng G

BÀI TOÁN
Viết chương trình kiểm tra tính liên thông của một đồ thị vô hướng A[i,j] với A[i,j] = 1 nếu có đường đi từ i đến j và ngược lại A[i,j] = 0 nếu không có đường đi từ i đến j.
Dữ liệu vào: cho trong file Bai2.inp.
- Dòng đầu ghi số n là số đỉnh của một đồ thị (0- Dòng i+1 ( ) 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”.

Ví dụ 1:
BAI2.INP
5
0 0 0 0 1
0 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
KQ: DO THI LIEN THONG

BAI2.INP
8
0 1 0 0 0 1 0 0
1 0 1 0 0 0 0 0
0 1 0 1 0 0 0 0
0 0 1 0 1 0 0 0
0 0 0 1 0 1 0 0
1 0 0 0 1 0 1 0
0 0 0 0 0 1 0 1
0 0 0 0 0 0 1 0
KQ: DO THI LIEN THONG

BAI2.INP
6
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
0 0 0 0 1 1
0 0 0 1 0 1
0 0 0 1 1 0
KQ: DO THI KHONG LIEN THONG

HƯỚNG DẪN THUẬT TOÁN
Ý tưởng: Sử dụng kỹ thuật loang.
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 tất cả các đỉ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 (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.

HƯỚNG DẪN CÀI ĐẶT
Tổ chức cấu trúc dữ liệu để lưu trữ sự đánh dấu các đỉnh của đồ thị.
 Ta tổ chức một mảng 1 chiều (char*DanhDau) để lưu trữ những đỉnh của đồ thị có được đánh dấu hay không. Chỉ số của mảng chính là chỉ số đỉnh của đồ thị.
 DanhDau[i]=0 nếu đỉnh i chưa được đánh dấu và DanhDau[i]=1 nếu đỉnh i đã được đánh dấu. Ví dụ: DanhDau[5]=1, DanhDau[3]=0 có nghĩa là đỉnh thứ 5 của đồ thị đã được dánh đấu và đỉnh thứ 3 của đồ thị chưa được dánh dấu.
 Trong thuật toán, trước tiên ta khởi tạo tất cả các đỉnh của đồ thị là chưa được đánh dấu. Nghĩa là DanhDau[i]=0, i=0..n-1.
- Dánh dấu đỉnh dầu tiên của đồ thị (DanhDau[0]=1).
- Từ đỉnh i đã đánh dấu (DanhDau[i]=1), ta đánh dấu đỉnh j (DanhDau[j]=1) nếu A[i][j] = 1 và j chưa được đánh dấu (DanhDau[j]=0). Cứ tiếp tục như vậy cho đến khi không thực hiện được nữa.
- Nếu đỉnh nào chưa đánh dấu (tồn tại DanhDau[k]=0, 0≤k

CHƯƠNG TRÌNH MẪU

Code:

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define TenFile "Bai2.inp"
/*Đọc file dữ liệu*/
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 kiểm tra tính liên thông: Nếu liên thông trả về giá trị 1, ngược lại trả về giá trị 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++)        //Khởi tạo mọi đỉnh chưa được đánh dấu
      DanhDau[i] = 0;
  DanhDau[0] = 1;        //Đánh dấu đỉnh đầu
  Dem++;            //Đểm số đỉnh đã đánh dấu là 1
  do { 
    ThanhCong =1;      //Giả sử không còn khả năng loang
      for(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;  //Thực tế còn khả năng loang
            Dem++;
            if(Dem == n) return 1;
        }
      }
  }while (ThanhCong == 0);  //Lặp lại cho đến khi không còn khả năng loang
  return 0;
}
/*Chương trình chính*/
void main() {
  clrscr();
  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();
}