Mô tả bài toán: Cho đồ thị vô hướng có trọng số G=(V,E) hãy tìm đường đi sao cho tất cả các đỉnh điều có đường đi với nhau và tổng trọng số của đường đi là nhỏ nhất. Tức là tìm đồ thị con liên thông G' ⊆ G sao cho tổng trọng số của G’ là nhỏ nhất.
Ý tưởng thuật toán:
Bước 0: khởi tạo tập cạnh tìm được là rỗng và 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 1 và 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.
Mô tả dữ liệu đầu vào và đầu ra của bài toán:
Dữ liệu vào: lưu trong tập tin Bai8.inp
- Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100)
- Dòng i+1 (1<=i <=n) lưu ma trận kề của đồ thị với 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 Kruskal.out
- Dòng đầu ghi trọng số nhỏ nhất của cây bao trùm.
- Các dòng còn lại lưu đường đi giữa đỉnh i nối với đỉnh j.
Ví dụ:
#include <stdio.h>
#include <values.h>
#define FileInt "Bai8.inp"
#define FileOut "Bai8.out"
typedef structEgde {
int x,y;
};
//đọc dữ liệu từ tập tin
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 tập tin
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);
}
void Kruskal(int **A, int n) {
int *D = new int[n];
Egde *L = new Egde[n-1];
int min = MAXINT, 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;
}
if(D[L[Dem].x] ==0 && D[L[Dem].y] == 0){
T++;
D[L[Dem].x] = D[L[Dem].y] = T;
}
if(D[L[Dem].x] == 0 && D[L[Dem].y] != 0){
D[L[Dem].x] = D[L[Dem].y];
}
if(D[L[Dem].x] != 0 && D[L[Dem].y] == 0){
D[L[Dem].y] = D[L[Dem].x];
}
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
int main() {
int **A,n;
Doc_File(A,n);
Kruskal(A,n);
delete *A;
return 0;
}
Từ khóa: ky thuat lap trinh, kỹ thuật lập trình, Kruskal, cây bao trùm tối thiểu, programming, algorithm, toán rời rạc, cây, cau truc du lieu, giai thuat.
Klik untuk melihat kode: