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 7. Thuật toán Kruskal tìm cây phủ tối tiểu

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 7. Thuật toán Kruskal tìm cây phủ tối tiểu

Bài gửi  admin on Sat Dec 19, 2009 1:01 pm

Ứng dụng thuật toán Kruskal


Một công ty cần thay toàn bộ hệ thống dây điện cho n phòng làm việc. Cho biết sơ đồ điện hiện có của n căn phòng này được biều diễn bằng ma trận A[i,j] trong đó:
- A[i,j]=A[j,i] chính là chiều dài dây điện nối liền giữa hai phòng i và j.
- A[i,j] = A[j,i] = 0 nếu i không nối liền với j.
Hãy lập trình tính độ dài cuả dây dẫn cần sử dụng sao cho cả n phòng điều có điện và số lượng này là ít nhất.
Chú ý: đồ thị đã cho là liên thông.
Dữ liệu vào: cho trong file Bai8.inp (đồ thị cho đã liên thông).
- Dòng đầu ghi số n là số đỉnh của một đồ thị (0- Dòng i+1 (1<= i <= n) 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: lưu trong file Bai8.out với nội dung sau:
- Dòng đầu lưu độ dài dây dẫn nhỏ nhất
- Các dòng còn lại lưu đường đi cần nối điện giữa đỉnh i nối với đỉnh j có trọng số A[i,j] (i -> j = A[j]).

Bai8.inp
5
0 3 3 2 2
3 0 2 3 8
3 2 0 1 4
2 3 1 0 4
2 8 4 4 0

Bai8.out
7
4 – 3
3 – 2
4 – 1
1 – 5

Bai8.inp
8
0 2 3 4 0 0 0 0
2 0 3 0 4 0 0 0
3 3 0 7 6 5 2 0
4 0 7 0 0 0 3 0
0 4 6 0 0 4 0 8
0 0 5 0 4 0 1 6
0 0 2 3 0 1 0 5
0 0 0 0 8 6 5 0

Bai8.out
20
1 - 2
1 - 3
3 - 7
7 - 6
7 - 4
2 - 5
7 - 8

Thuật toán Kruskal tìm cây phủ tối tiểu
Bước 0: Khởi tạo tập cạnh tìm được là rỗng. Chuyển sang bước 1.
Bước 1: Chọn một cạnh có trọng số nhỏ nhất sao cho khi đưa cạnh này vào tập cạnh tìm được không tạo thành chu trình. Tăng số cạnh tìm được lên 1và chuyển sang bước 2.
Bước 2: Nếu số cạnh tìm được bằng n-1 thuật toán kết thúc, ngược lại quay về bước 1.

HƯỚNG DẪN CÀI ĐẶT

Ta tổ chức mảng 1 chiều D để đánh dấu . Nếu D[i]=T thì đỉnh i thuộc vào cây thứ T, D[i] = 0 thì đỉnh i chưa thuộc vào cây.
Bước 1: Tìm min{A[i][j]}j=1..n, i=1..n ngoại trừ điều kiện D[i]=D[j]<>0. Vì khi thỏa mãn điều kiện trên đỉnh i,j đã thuộc vào một cây do đó khi lấy thêm cạnh này chúng sẽ tạo thành chu trình. Đỉnh i,j tìm được thoả mãn một trong các trường hợp sau:
- Nếu D[i]=D[j]=0, đỉnh i,j chưa thuộc vào cây nên khi lấy 2 đỉnh này vào tập cạnh ta cho chúng thuộc vào 1 cây mới. Nghĩa là số cây T++ và D[i]=D[j]=T.
- Nếu D[i]=0 và D[j]0, đỉnh i chưa thuộc vào cây và j đã thuộc vào cây. Ta lấy đỉnh i vào cây tương ứng với cây của đỉnh j. Nghĩa là gán D[i]=D[j].
- Nếu D[i]<>0 và D[j]=0, đỉnh j chưa thuộc vào cây và i đã thuộc vào cây. Ta lấy đỉnh j vào cây tương ứng với cây của đỉnh i. Nghĩa là gán D[j]=D[i].
- Nếu D[i]<>D[j] và D[i]<>0 và D[j]<>0, đỉnh i thuộc vào cây và đỉnh j cũng thuộc vào cây nhưng cây i và j là 2 cây khác nhau. Ta tiến hành ghép cây nghĩa là ghép 2 cây chứa i,j thành 1 cây mới.
Temp = D[i]
for(int i=0 ; iif(D[i]==Temp) D[i]=D[j]
Tăng số cạnh tìm được lên 1 (Dem++).
Bước 2: Nếu Dem = n-1 thì thuật toán kết thúc.
[i]Chú ý:
trong qua trình tìm có thể tạo thành rất nhiều cây nhưng kết quả tìm được cuối cùng là một cây thông qua quá trình ghép cây.

Code:

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <values.h>
#define FileInt "Bai8.inp"
#define FileOut "Bai8.out"

/*Lưu lại những cạnh đã đi qua x->y*/
typedef struct Egde {
   int x,y;
};
/*Doc dữ liệu từ file*/
void Doc_File(int **A,int &n){
   FILE*f = fopen(FileInt,"rb");
   fscanf(f,"%d",&n);
   *A = new int [n];
   for(int i =0;i<n;i++) {
      A[i] = new int [n];
      for(int j =0;j<n;j++) {
         fscanf(f,"%d",&A[i][j]);
      }
   }
   fclose(f);
}
/*Ghi dữ liệu ra file*/
void Ghi_File(Egde*L,int n,int Sum) {
   FILE*f = fopen(FileOut,"wb");
   fprintf(f,"%d\n",Sum);
   for(int i =0; i<n-1; i++)
      fprintf(f,"%d - %d\n",L[i].x+1,L[i].y+1);
   fclose(f);
}
/*Thuật toán Kruskal  */
void Kruskal(int **A, int n){
   char *D = new char[n];
   Egde *L = new Egde[n-1];
   int min, Dem = 0, Sum = 0, T = 0, Temp;
   for(int i=0; i<n; i++)
      D[i] = 0;   
   do{
      min = MAXINT;
      for( i=0; i<n; i++)
      for(int j=0; j<n; j++)
      if(A[i][j]>0 && min>A[i][j]&& !(D[i]!=0 && D[i]==D[j])) {
            min = A[i][j];
            L[Dem].x = i;
            L[Dem].y = j;
      }
      /*Tạo ra cây mới*/
      if(D[L[Dem].x] ==0 && D[L[Dem].y] == 0){
         T++;
         D[L[Dem].x] = D[L[Dem].y] = T;
      }
      /*Đưa đỉnh tương ứng vào cây*/
      if(D[L[Dem].x] == 0 && D[L[Dem].y] != 0)
         D[L[Dem].x] = D[L[Dem].y];
      /*Đưa đỉnh tương ứng vào cây*/
      if(D[L[Dem].x] != 0 && D[L[Dem].y] == 0)
         D[L[Dem].y] = D[L[Dem].x];
      /*Ghép 2 cây thành 1 cây mới*/
      if(D[L[Dem].x] != D[L[Dem].y] && D[L[Dem].y]!=0)  {
         Temp = D[L[Dem].x];
         for( i=0; i<n; i++)
         if(Temp==D[i])
            D[i]=D[L[Dem].y];
      }
      Sum+=min;
      Dem++;
   } while(Dem<n-1);
   Ghi_File(L,n,Sum);
}
/*Chương trình chính*/
void main() {
   int **A,n;
   Doc_File(A,n);
   Kruskal(A,n);
   delete *A;
}


Được sửa bởi Admin ngày Thu May 26, 2011 8:35 am; sửa lần 1.

lkngan23
Nhập môn
Nhập môn

Tổng số bài gửi : 1
Points : 1
Join date : 22/05/2011

Re: Bài 7. Thuật toán Kruskal tìm cây phủ tối tiểu

Bài gửi  lkngan23 on Sun May 22, 2011 11:02 pm

Cho e hỏi trong phần code của thuật toán kruskal thì có dòng min=MAXINT vậy MAXINT là biến lấy ở đâu?

Code:
  do{
      [color=red]min = MAXINT;[/color]
      for( i=0; i<n; i++)
      for(int j=0; j<n; j++)
      if(A[i][j]>0 && min>A[i][j]&& !(D[i]!=0 && D[i]==D[j])) {
            min = A[i][j];
            L[Dem].x = i;
            L[Dem].y = j;
      } 

Đọc rồi mà không hiểu! Em Cám ơn!
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ơ

Re: Bài 7. Thuật toán Kruskal tìm cây phủ tối tiểu

Bài gửi  admin on Wed May 25, 2011 8:04 am

lkngan23 đã viết:Cho e hỏi trong phần code của thuật toán kruskal thì có dòng min=MAXINT vậy MAXINT là biến lấy ở đâu?

MAXINT là giá trị lớn nhất của số nguyên nằm trong thư viện Values.h . Bạn nên nhấn F1 đọc Help trên trương trình.

binmaster
Nhập môn
Nhập môn

Tổng số bài gửi : 3
Points : 3
Join date : 09/07/2011

Re: Bài 7. Thuật toán Kruskal tìm cây phủ tối tiểu

Bài gửi  binmaster on Sat Jul 09, 2011 10:13 pm

Mình đang học thuật toán này mà vẫn chưa hiểu, chạy code của admin thì soát ko lỗi nhưng khi chạy thì bị lỗi Sad
Mình chạy trên dev-C++, admin xem lại code coi
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ơ

Re: Bài 7. Thuật toán Kruskal tìm cây phủ tối tiểu

Bài gửi  admin on Sun Jul 10, 2011 9:56 am

Code nay không có lỗi, bạn thử chạy trên Turbo C thử xem.

Sponsored content

Re: Bài 7. Thuật toán Kruskal tìm cây phủ tối tiểu

Bài gửi  Sponsored content


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