Search
 
 

Display results as :
 


Rechercher Advanced Search

Latest topics
» 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

» 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

Shopmotion


Affiliates
free forum


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

Go down

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

Post  Admin on Wed Jun 15, 2011 10:42 pm

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.

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

Tổng số bài gửi : 782
Join date : 2009-08-15

View user profile http://hackis.forumvi.com

Back to top Go down

Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum