Gia sư Cần Thơ, Dạy Kèm Cần Thơ

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


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

Share
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 36
Đến từ : Cần Thơ

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

Bài gửi  admin on Thu May 26, 2011 8:41 am

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

    Hôm nay: Mon Nov 20, 2017 4:26 pm