Search
 
 

Display results as :
 


Rechercher Advanced Search

Latest topics
» NewBlueFx TotalFX Windows-FL | 1.11 GB
Tue Dec 17, 2013 12:42 pm by titquarra

» NewBlueFx TotalFX Windows-FL | 1.11 GB
Tue Dec 17, 2013 12:42 pm by titquarra

» Celebrity.Sex.Tape.UNCUT.&.UNRATED.2012.720p.BRrip.x264.YIFY.mp4
Tue Dec 17, 2013 8:32 am by titquarra

» Maya Autodesk Personal Learning Edition 8.5
Tue Dec 17, 2013 7:47 am by titquarra

» Tuyệt Kỹ Đong Giai Chân Kinh (tuyệt Kỹ cua trai)
Thu Aug 23, 2012 5:38 am by Admin

» Tuyệt kỹ cua giai
Thu Aug 23, 2012 5:36 am by Admin

» NETCAT.........
Mon Aug 13, 2012 6:35 am by Admin

» Bảo mật CSDL bằng phương pháp mã hóa.
Tue Apr 17, 2012 10:04 pm by Admin

» Hàm mã hóa MD5 bằng JavaScript
Tue Apr 17, 2012 10:03 pm by Admin

Shopmotion


Affiliates
free forum


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

View previous topic View next topic Go down

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

Post  Admin on Wed Jun 15, 2011 10:49 pm

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();
}

Admin
Admin

Tổng số bài gửi : 782
Join date : 2009-08-15

View user profile http://hackis.forumotion.com

Back to top Go down

View previous topic View next topic Back to top


 
Permissions in this forum:
You cannot reply to topics in this forum