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


Tìm đỉnh có bậc lớn nhất trên đồ thị vô hướng G

View previous topic View next topic Go down

Tìm đỉnh có bậc lớn nhất trên đồ 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 tìm bậc cao nhất của đỉnh trong đồ thị với đồ 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 Bai1.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 số bậc cao nhất của đỉnh trong đồ thị đã cho.

Ví dụ:
6
0 1 1 0 0 0
1 0 0 1 1 0
1 0 0 0 1 0
0 1 0 0 1 0
0 1 1 1 0 1
0 0 0 0 1 0

Kết quả:BAC CAO NHAT : 4

HƯỚNG DẪN
Ý tưởng: tổng số phần tử khác không trên dòng i của ma trận liên kết chính là số bậc tương ứng của đỉnh i (i=1..n).
Trước tiên, ta gián bậc lớn nhất (BLN) của đỉnh bằng 0, tính bậc của từng đỉnh bằng cách đếm các chỉ số khác không của ma trận liên kết theo dòng và so sánh với bậc lớn nhất. Nếu bậc của đỉnh tương ứng lớn hơn BLN ta gián BLN bằng bậc của đỉnh tương ứng. Thuật toán kết thúc khi ta đã duyệt qua tất cả các đỉnh của đồ thị.

CHƯƠNG TRÌNH MẪU

Code:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <values.h>
#define TenFile "Bai1.inp"
/*Đọc file dữ liệu bài toán*/
void Doc_File(int **A,int &n) {
  FILE*f = fopen(TenFile,"rb");      //Mở file dữ liệu
  fscanf(f,"%d",&n);            //Đọc số đỉnh của đồ thị
  *A = new int [n];      //Cấp phát số vùng nhớ tương ứng theo chiều ngang
  cout<<"Ma Tran Lien Ket Cua Do Thi";
  for(int i =0;i<n;i++) {
      A[i] = new int [n];        //Cấp phát vung nhớ theo chiều rộng
      cout<<endl;
      for(int j =0;j<n;j++) {
        fscanf(f,"%d",&A[i][j]);
        cout<<"  "<<A[i][j];
      }
  }
  fclose(f);              //Đóng file dữ liệu
}
/*Hàm trả về bậc lớn nhất của đỉnh*/
int BacLonNhat(int**A,int n) {
  int max = 0,Bac;
  for(int i = 0; i<n; i++) {
      Bac = 0;
      for(int j = 0; j<n; j++)
      if(A[i][j]>0)        //Tính bậc của từng đỉnh
        Bac++;
      if(Bac > max)    max = Bac;
  }
  return max;            //Trả về bậc lớn nhất 
}
/*Chương trình chính*/
void main() {
  clrscr();
  int **A,n;
  Doc_File(A,n);
  cout<<"\n1. Bac Lon Nhat Cua Dinh: "<<BacLonNhat(A,n);
  delete*A;
  getch();
}
Xử lý mở rộng:
/*Hàm trả về bậc nhỏ nhất của đỉnh*/
int BacNhoNhat(int**A,int n){
  int min = MAXINT,Bac;
  for(int i = 0; i<n; i++) {
      Bac = 0;
      for(int j = 0; j<n; j++)
      if(A[i][j]>0)
        Bac++;
      if(Bac < min)
        min = Bac;
  }
  return min;
}
/*Hàm trả về tổng bậc của đồ thị*/
int TongBac(int**A,int n){
  int Tong = 0;
  for(int i = 0; i<n; i++)
  for(int j = 0; j<n; j++)
  if(A[i][j]>0)
      Tong++;
  return Tong;
}
/*Thủ tục liệt kê các đỉnh có bậc nhỏ nhất*/
void DinhBacNhoNhat(int**A, int n){
  int min = BacNhoNhat(A,n), Bac;
  for(int i = 0; i<n; i++) {
      Bac = 0;
      for(int j = 0; j<n; j++)
      if(A[i][j]>0)
        Bac++;
      if(Bac == min)
        cout<<"  "<<i+1;
  }
}
/*Thủ tục liệt kê các đỉnh có bậc lớn nhất*/
void DinhBacLonNhat(int**A, int n){
  int max = BacLonNhat(A,n), Bac;
  for(int i = 0; i<n; i++) {
      Bac = 0;
      for(int j = 0; j<n; j++)
      if(A[i][j]>0)
        Bac++;
      if(Bac == max)
        cout<<"  "<<i+1;
  }
}
/*Thủ tục liệt kê các đỉnh bậc chẵn và số đỉnh bậc chẵn*/
void DinhBacChan(int**A, int n) {
  int Bac,Tong=0;
  for(int i = 0; i<n; i++) {
      Bac = 0;
      for(int j = 0; j<n; j++)
      if(A[i][j]>0)
        Bac++;
      if(Bac%2==0) {
        cout<<"  "<<i+1;
        Tong++;
      }
  }
  cout<<"\n\t So Dinh Bac Chan: "<<Tong;
}
/*Thủ tục liêt kê các đỉnh bậc lẻ và số đỉnh bậc lẻ*/
void DinhBacLe(int**A, int n){
  int Bac,Tong=0;
  for(int i = 0; i<n; i++) {
      Bac = 0;
      for(int j = 0; j<n; j++)
      if(A[i][j]>0)
        Bac++;
      if(Bac%2==1) {
        cout<<"  "<<i+1;
        Tong++;
      }
  }
  cout<<"\n\t So Dinh Bac Le: "<<Tong;
}

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