Search
Latest topics
Ứng dụng thuật toán Prim
Page 1 of 1
Ứng dụng thuật toán Prim
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[i][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 Prim tìm cây phủ tối tiểu.
Bước 1: Xuất phát từ đỉnh k bất kỳ (thông thường chọn đỉnh đầu tiên) chọn một cạnh có trọng số nhỏ nhất liền kề với đỉnh k (min{A[k][j]}j=1..n) ta đánh dấu 2 đỉnh đi qua cạnh đó
và số cạnh tìm được là 1. Chuyển sang bước 2.
Bước 2: Tìm cạnh nhỏ nhất của đồ thị với điều kiện cạnh tìm được phải có 1 đỉnh chưa đánh dấu và 1 đỉnh đã đánh dấu (min{A[i][j]}j=1..n, i=1..n sao cho i đánh đấu và j chưa đánh dấu) để tránh trường hợp tạo thành chu trình. Ta tăng số cạnh tìm được lên 1 và chuyển sang bước 3.
Bước 3: Nếu số cạnh tìm được bằng n-1 kết thúc thuật toán, ngược lại quay về bước 2.
HƯỚNG DẪN CÀI ĐẶT
Ta tổ chức mảng 1 chiều D để đánh dấu . Nếu D[i]=1 đỉnh i được đánh dấu và D[i]=0 nếu i chưa được đánh dấu.
Bước 1: Tìm min{A[1][j]}j=1..n. Sau đó gán D[1]=D[j]=1 (đánh dấu 2 đỉnh 1,j) và cho số cạnh tìm được bằng 1 (Dem=1).
Bước 2: Tìm min{A[i][j]}j=1..n, i=1..n với điều kiện D[i]=1 và D[j]=0. Sau đó gán D[j]=1 (đánh dấu đỉnh j vừa tìm được) và tăng số cạnh lên 1 (Dem++).
Bước 3: Nếu Dem = n-1 thì thuật toán kết thúc.
- 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[i][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 Prim tìm cây phủ tối tiểu.
Bước 1: Xuất phát từ đỉnh k bất kỳ (thông thường chọn đỉnh đầu tiên) chọn một cạnh có trọng số nhỏ nhất liền kề với đỉnh k (min{A[k][j]}j=1..n) ta đánh dấu 2 đỉnh đi qua cạnh đó
và số cạnh tìm được là 1. Chuyển sang bước 2.
Bước 2: Tìm cạnh nhỏ nhất của đồ thị với điều kiện cạnh tìm được phải có 1 đỉnh chưa đánh dấu và 1 đỉnh đã đánh dấu (min{A[i][j]}j=1..n, i=1..n sao cho i đánh đấu và j chưa đánh dấu) để tránh trường hợp tạo thành chu trình. Ta tăng số cạnh tìm được lên 1 và chuyển sang bước 3.
Bước 3: Nếu số cạnh tìm được bằng n-1 kết thúc thuật toán, ngược lại quay về bước 2.
HƯỚNG DẪN CÀI ĐẶT
Ta tổ chức mảng 1 chiều D để đánh dấu . Nếu D[i]=1 đỉnh i được đánh dấu và D[i]=0 nếu i chưa được đánh dấu.
Bước 1: Tìm min{A[1][j]}j=1..n. Sau đó gán D[1]=D[j]=1 (đánh dấu 2 đỉnh 1,j) và cho số cạnh tìm được bằng 1 (Dem=1).
Bước 2: Tìm min{A[i][j]}j=1..n, i=1..n với điều kiện D[i]=1 và D[j]=0. Sau đó gán D[j]=1 (đánh dấu đỉnh j vừa tìm được) và tăng số cạnh lên 1 (Dem++).
Bước 3: Nếu Dem = n-1 thì thuật toán kết thúc.
- 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 Prim*/
void Prim(int **A, int n){
char *D = new char[n]; /*Dánh dấu đỉnh*/
Egde *L = new Egde[n-1]; /*Lưu đường đi */
int min = MAXINT, Dem = 0, Sum = 0;
/*Khoi tạo giá trị cho mảng đánh dấu*/
for(int i=0; i<n; i++)
D[i]=0;
/*Tìm cạnh nhỏ nhất đầu tiên xuất phát từ đỉnh 1*/
for(int j=1; j<n; j++)
if(min>A[0][j] && A[0][j]!=0){
min = A[0][j];
L[0].y = j;
}
L[0].x = 0;
D[0] = D[L[0].y] = 1;
Sum+=min;
Dem++;
/*Thực hiện cho đến khi số cạnh tìm được là n-1 cạnh*/
do{
min = MAXINT;
for( i=0; i<n; i++)
if(D[i]==1)
for( j=0; j<n; j++)
if(A[i][j]>0 && min>A[i][j] && D[j]==0){
min = A[i][j];
L[Dem].x = i;
L[Dem].y = j;
}
Sum+=min;
D[L[Dem].y] = 1;
Dem++;
} while(Dem<n-1);
Ghi_File(L,n,Sum); /*Ghi kết quả tìm được vào file*/
}
/*Chương trình chính*/
void main() {
int **A,n;
Doc_File(A,n);
Prim(A,n);
delete *A;
}
Similar topics
» Tìm Cây Phụ Tối Tiểu (Thuật Toán PRIM)
» Xét Tính Liên Thông Của Đồ Thị Sử Dụng Thuật Toán DFS và BFS
» Ứng dụng thuật toán DIJKSTRA tìm đường đi ngắn nhất
» Thuật toán QuickSort
» Thuật toán Dijkstra
» Xét Tính Liên Thông Của Đồ Thị Sử Dụng Thuật Toán DFS và BFS
» Ứng dụng thuật toán DIJKSTRA tìm đường đi ngắn nhất
» Thuật toán QuickSort
» Thuật toán Dijkstra
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum
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
» Giá của món quà
Fri Apr 13, 2012 6:01 am by Admin
» Sẽ chỉ yêu ai?
Fri Apr 13, 2012 6:01 am by Admin
» Cách đọc bảng chữ cái!
Thu Apr 12, 2012 10:37 pm by Admin
» Gắn trojan, keylog, virus vào website, forum
Tue Apr 10, 2012 1:14 am by Admin